Bitwise AND of Numbers Range

Omar Faroque
Sep 7, 2018 · 2 min read

Before moving forward, let's talk about AND operation. AND, literal meaning, if two entity agrees on something (true/false or same side) then the result is the same. Otherwise, results would be different obviously.

As an example, let say number 5(101) and 7(111), if we do bitwise AND we will get 101.

Let's say another example for this particular problem:

For number 26 to 30
Their binary form are:
11010
11011
11100
11101
11110

Because we are trying to find bitwise AND, so if any bit there are at least one 0 and one 1, it always 0. In this case, it is 11000.
So we are go to cut all these bit that they are different. In this case, we cut the right 3 bit.

How to cut the right 3bit? If we keep moving to the right(right shift) for both numbers, at some point, we will have the same number.

26: 11010->01101->00111->00011

30: 11110->01111->00111->00011

After three moves to the right, we see the same. Now see the java code:

class Solution {
public int rangeBitwiseAnd(int low, int high) {
int count=0;// initially counter is 0
while(low!=high){
low >>= 1; //right shift
high >>= 1; //right shift
count++; // increase the counter to count how many shift was needed
}
System.out.println(low << count);
return low<<count;// Result is left shift of low count times.

}
}

Algorithm and DataStructure

Algorithm and Data Structure solutions

Omar Faroque

Written by

Enterprise Applications Architectecture | JAVA | Parallel & Distributed Programing | Node.js | IoT | Golang |Starter|Microservices

Algorithm and DataStructure

Algorithm and Data Structure solutions

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade