Bitwise AND of Numbers Range Problem

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:

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

Example 2:

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

Example 3:

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]:

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

Java

public int rangeBitwiseAnd(int left, int right) {
	while(right > left) {
		right = right & (right-1);
	}
	return left&right;
}

We don’t have to return left&right:

public int rangeBitwiseAnd(int left, int right) {
	int ans = right;
	while(right > left) {
		ans = right & (right-1);
		right = ans;
	}
	return ans;
}

Further Optimization

this can be optimised further, if there exists 2^n in the range.. result would be zero. If you see example above, 8&7 = 0.

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;
}