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).

Click to copy

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?

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