BITWISE AND(&) for Range of Numbers

Question

Given two numbers L & R , Find Bitwise AND of all numbers lying between L and R inclusive

Constraints 1<= L,R <= (2^32).

LL step = 1;
    while(L!=R)
    {
        L/=2; R/=2; step*=2;
    }
    cout<<L*step<<endl;

Can anybody help me with the explanation or logic behind the above code?

Yeta

Answer 1

So Yes, it is a bit hard and needs sketching on paper. Once you get the idea it is simple. I will start with English explanations then simple example. The most important thing is to release your mind from the fact that we are bit-wising two numbers and think about the numbers in between.

First, Let's say some rules: 1) If two numbers are equal, no numbers will be between them. 2) If Two numbers are not Equal, The consecutive number between them Will contain ZERO at each digit, thus their bitwise AND will be ZERO.

Before going into the example, We should explain the simple algorithm above.

1) Each division by two means remove a binary digit from the right of the numbers. (This is how division by two means in binary). 2) Each time we divide, we double the step variable. Simple, the step variable is more like a counter that holds the top most digit value just before the two numbers became equal.

Suppose we have the following example:

L : 11110001 R : 11110011

S=1 (00000001 in binary)

---

Applying your algorithm on these values:

Since L and R are not equal yet, chop a single binary digit from each (divide each by 2) and multiply S by 2; In the first round they become

L : 1111000 R : 1111001

S=2 (00000010 in binary)

Since they are not equal yet, do it again, and the result is:

L : 111100 R : 111100

Now they are equal, the loop breaks and the result

is the Left number (or the right since they are equal) * S value.

When we multiple in Binary we add a zero to the right. Here we need 3 zeros since S is 00000010

11110000 which is as expected.

Conclusion: Keep chopping by dividing until both are equal and nothing is between them. While you do that keep updating which step you are in :)

Riverhead

Answer 2

First let's think what does bitwise AND do to two numbers, for example ( 0b means base 2)

4 & 7 = 0b100 & 0b111 = 0b100
5 & 7 = 0b101 & 0b111 = 0b101
5 & 6 = 0b101 & 0b110 = 0b100

The operator & is keeping those bits which is set in both number.

For several numbers, the operator & is keeping those bits which is 1 in every number.

In other word, a bit is 0 in any number will result in 0 in the answer's corresponding bit.

Now consider a range

[m = 0bxyz0acd, n=0bxyz1rst] here xyzpacdrst all are digits in base 2.

We can find two numbers that are special in the range [m, n]

(1) m' = 0bxyz0111 (2) n' = 0bxyz1000 The bitwise AND of all the numbers in range [m, n] is just the bitwise AND of the two special number

rangeBitwiseAnd(m, n) = m' & n' = 0bxyz0000 This tells us, the bitwise and of the range is keeping the common bits of m and n from left to right until the first bit that they are different, padding zeros for the rest.

Bole

Answer 3

When we do a '&' of a range of number in the resulting answer if a bit is 0 that means that bit was 0 once. so we can right shift each bit until the point both value are not same .When both value are same then left shift the total number of bits that were different.The code for that is

    class Solution {
        public int rangeBitwiseAnd(int m, int n) {

            // if m !==n that means one of the bits is 0 so keep right shifting 
           //untill all the bits in both are same  and when they are same number of 
           //shift will be equal to number of bits not same just right shift it then

            int s = 0;
            while(m !=n){
                m =  m>>1;
                n = n>>1;

                s++;
            }
             return (m<<s);
        }
    }

Deepsea