Problem

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

Examples

Example 1:

1
2

Input: left = 5, right = 7
Output: 4

Example 2:

1
2

Input: left = 0, right = 0
Output: 0

Example 3:

1
2

Input: left = 1, right = 2147483647
Output: 0

Solution

Method 1 - Bitwise and Operator

Bitwise-AND of any two numbers will always produce a number less than or equal to the smaller number.

Consider the following example, for desired range [5, 12]:

1
2
3
4
5
6
7
8

12 ---- 1100
11 ---- 1011
10 ---- 1010
9  ---- 1001
8  ---- 1000
7  ---- 0111
6  ---- 0110
5  ---- 0101

Starting from 12, the loop will first do 12 & 11 = 8

Next iteration, the loop will do 8 & 7 = 0

why did we skip anding of 10,9? Because even if we did so, the result would eventually be and'ed with 8 whose value would be lesser than equal to 8.

Hence, you start from the range end and keep working your way down the range till you reach the start.

Code

1
2
3
4
5
6

public int rangeBitwiseAnd(int left, int right) {
	while(right > left) {
		right = right & (right-1);
	}
	return left&right;
}
 
1
2
3
4
5
6
7
8

public int rangeBitwiseAnd(int left, int right) {
	int ans = right;
	while(right > left) {
		ans = right & (right-1);
		right = ans;
	}
	return ans;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

public int rangeBitwiseAnd(int left, int right) {
    //~ find next 2^n bigger than left and if that is within the range result would be zero
    int psq = Integer.highestOneBit(left); 
    int next = psq << 1;
    if(next > left && next <= right) {
	    return 0; 
	}
    
    while(left < right)  right = right&(right-1);
    
    return right;
}