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:
-K Himaanshu Shuklaa
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
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
No comments:
Post a Comment