#LeetCode: Java Solution of Bitwise AND of Numbers Range problem

Bitwise AND of Numbers Range
Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

Example 1: Input: [5,7], Output: 4
Example 2:Input: [0,1], Output: 0

Reference:

Decimal No.	4-bit Binary No.
0	0
1	1
2	10
3	11
4	100
5	101
6	110
7	111
8	1000
9	1001
10	1010
11	1011
12	1100
13	1101
14	1110
15	1111
16	0001 0000
17	0001 0001

Algorithm
1. FYI, as per the binary logic 0 AND 0 is 0, 0 AND 1 is 0, 1 AND 0 is 0, 1 AND 1 is 1.
2. To solve this we will be using bitwise operators > > (left shift) and < < (right shift). Lets say m is 1110, if we do m > > it will return 111 and if we do m < < it will return 110.
3. Create a variable (shiftCounter) which will maintain the number of shifts.
4. In a while loop, we will check if m is less than n. We need to left shift m and n, increment 'shiftCounter'. There will be a situation when m will become equal to n
5. After this we will right shift n (or m) for 'shiftCounter' and return n (or m).

e.g: lets say m is 9 and n is 12. Binary of 9 is 000001001 and 12 is 00001100. shiftCounter=0
1). m is less than n, left shift both m and n. m=00000100 (i.e 4) and n=0000110 (i.e 6), shiftCounter=1
2). Since m is less than n, left shift both m and n. m=0000010 (i.e 2) and n=000011 (i.e 3), shiftCounter=2
3).  Again m is less than n, left shift both m and n. m=000001 (i.e 1) and n=00001 (i.e 1), shiftCounter=3.
4). While loop will end, because now m and n are equal.
5). We will now right shift n (or m) 3 times (because shiftCounter=3), this will give us n=00001000 (i.e 8). So the answer will be 8.

GIT URL: Java Solution of Leet Code's Bitwise AND of Numbers Range problem

Java Solution

-K Himaanshu Shuklaa