You are given a number range, you need to find the bitwise and of all the numbers in the range.
Example:
[5, 7]
The bitwise and of 5, 6, 7 will be 4.
The solution is very simple, once you understand the concept below:
Let’s take small example and try to understand.
We shall find bitwise & of the range 4, 5, 6, 7.
As you see that bitwise and will return 1 if all the bits are 1.
Again consider the range 8, 9, 10, 11, 12
Here also the pattern is the same. You see that except the most significant bit, all other bits are zero.
Once solution can be doing bit by bit & operation. But this is not efficient.
And the only time we get 1, is if both the numbers m and n are same.
So what we can do is, we can right shift both the digits by 1, till both of the digits become same. We should also keep track of how much shift has been done.
Then, when both the numbers become same, we can left shift the number of times we performed right shift. Hence we arrive at the solution.
Solution in C++
#include<iostream>
using namespace std;
int range_bitwise_and(int m, int n)
{
int shift = 0;
while (m != n)
{
shift++;
m = m >> 1;
n = n >> 1;
}
return m << shift;
}
int main()
{
int num_1 = 5;
int num_2 = 7;
cout<<"solution = "<<range_bitwise_and(num_1, num_2)<<endl;
}
Output:
solution = 4
