CODEWITHSUNDEEP
algorithmbitwise-operatorsbit
godfather
godfather

Reputation: 19

AND of all natural numbers lying between A and B both inclusive

We are required to compute the bit wise AND amongst all natural numbers lying between A and B, both inclusive.I came across this problem on a website and here is the approach they used but i couldn't understand the method.Can anyone explain this more clearly with an example ?

In order to solve this problem, we just need to focus on the occurrences of each power 2, which turn out to be cyclic. Now for each 2^i(the length of the cycle will be 2^(i+1) having 2^i zeros followed by same number of ones) we just need to compute if 1 remains constant in the given interval, which is done by simple arithmetic. If so, that power of 2 will be present in the answer, otherwise it won't.

Upvotes: 0

Views: 73

Answers (1)

maraca
maraca

Reputation: 8763

Let's count (unsigned) with 3 bits to visualize some numbers first:

000 = 0
001 = 1
010 = 2
011 = 3
100 = 4
101 = 5
110 = 6
111 = 7

If you look at the columns, you can see that the lowest bit is alternating with a cycle of 1, the next with a cycle of 2, then 4, and the nth lowest bit is alternating with a cycle of 2^(n-1).

As soon as a bit was 0 once it is always 0 (because 0 and whatever is 0).

You could also say the nth bit is only 1 if the nth bit of A and B is 1 and d < 2^(n-1). In other words a bit will only be 1 if it is 1 at the beginning and the end and didn't had time to change to 0 in between because its cycle is too large.

Upvotes: 2

Related Questions