[Algorithm] Bitwise AND of Numbers Range

Bitwise AND of Numbers Range

Problem statement

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4.

Solution: Detect bit change

A brutal force way of solving it is O(n), simply loop over the whole range. Clearly we can do better. Note that we are doing an AND operation which means 0 is dominating. So the goal for us would naturally to find whether 0 will occur on specific bit.

How do we determine this?

There are two situations where one specific bit is 0:

1) The bit is 0 at the lower bound or upper bound already
2) The bit will change from 1 to 0 in the range.

First scenario is easy, doing lower bound & upper bound will set 0 on those bits. 

The second scenario can be determined by calculating the transform distance of 1 to 0.

For bit 0: transforming from 1 to 0 takes 1 step.

For bit 1: tranforming from 010 to 100 takes 2 steps: 010 -> 011 -> 100

For bit 2: transforming form 0100 to 1000 takes 4 steps: 0100 -> 0101 -> 0110 -> 0111 -> 1000.

...

Indeed for i^th bit to transform from 1 to 0 takes 2ⁱ steps at most. The upper bound of change is 2ⁱ at i^th bit and if the i^th bit is 0 already it will stay at 0, becausing AND operation.

So we can simply check the difference between the upper and lower bound to see how far it can reach, in other words set all i^th bits to be 0 where 2ⁱ < diff.

Code implementation.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

class Solution { public: int rangeBitwiseAnd(int m, int n) { long long diff = n - m; long long res = m & n; long long base = 1; while(1) { if (base < diff) { res &= (~base); base <<= 1; } else { break; } } return res; } };