BITWISE AND (&) for a range of numbers

Question

Given the two numbers L and R, find the bitwise AND of all numbers 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 someone help me with the explanation or logic of the above code?

Answer 1

So yes, it’s a little complicated and requires paper sketches. Once you get the idea, it's simple. I will start with English explanations, and then a simple example. The most important thing is to free your mind from the fact that we are bits of two numbers and think about the numbers between them.

First, let's say some rules: 1) If two numbers are equal, there will be no numbers between them. 2) If the two numbers are not equal, the serial number between them will contain ZERO on each digit, so their bitwise AND will be ZERO.

Before moving on to an example, we must explain the simple algorithm above.

1) Each division in two ways removes the binary digit to the right of the numbers. (This is like dividing by two means in binary format). 2) Each time we share, we double the step variable. A simple, step variable is more like a counter that holds the highest value of a digit before both numbers become equal.

Suppose we have the following example:

L: 11110001 R: 11110011

S = 1 (00000001 in binary format)

---

Applying your algorithm to these values:

Since L and R are not equal yet, cut one 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 format)

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

L: 111100 R: 111100

Now they are equal, cycle break and result

- left number (or right, since they are equal) * S.

When we are multiple in binary, add zero to the right. Here we need 3 zeros, since S is 00000010

11110000, as expected.

Conclusion: continue to grind, dividing, until both are equal and there is nothing between them. While you do this, update at what stage you are :)

Answer 2

First think that it is bitwise and does up 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 and saves those bits that are set in both numbers.

For several numbers, the operator and saves these bits equal to 1 in each number.

In other words, the bit is 0 in any number, the result will be 0 in the corresponding bit of the answer.

Now consider the range

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

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

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

rangeBitwiseAnd (m, n) = m 'and n' = 0bxyz0000 This tells us that the bit value and range support the normal bits m and n from left to right until the first bit becomes different, the rest remains for the rest.