Algorithms to Compute the Bitwise AND of Numbers in a Range

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

Example 1:
Input: [5,7]
Output: 4

Example 2:
Input: [0,1]
Output: 0

Bruteforce Algorithm to Compute the Bitwise AND of numbers within a range

The most intutuive solution is to apply the Bitwise AND for each numbers in a range, and the complexity will be O(N) where N is the total of the integers between M and N.

1
2
3
4
5
6
7
8
9
10

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int res = m;
        for (int i = m + 1; i <= n; ++ i) {
            res &= i;
        }
        return res;
    }
};

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int res = m;
        for (int i = m + 1; i <= n; ++ i) {
            res &= i;
        }
        return res;
    }
};

For inputs such as (0, 2147483647), the above bruteforce algorithm is inefficient to give a answer as all the numbers are iterated.

Compute the Common Prefix in Binary

Let’s take the numbers from 4 to 7 in binary, and do a bitwise AND.

0100
0101
0110
0111

The common prefix is 01, which converted to binary is 4. Thus, we can find the common prefix of all numbers between m and n using the following O(1) algorithm (both constant in time and space).

While m is smaller than n, we shift both numbers one position to the right (effectively dividing both numbers to two).

m = 0100, n = 0111, shift = 0
m = 0010, n = 0011, shift = 1
m = 0001, n = 0001, shift = 2

Thus, the answer is 1 << 2 = 0100

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int shift = 0;
        while (m < n) {
            m >>= 1;
            n >>= 1;
            shift ++;
        }
        return m << shift;
    }
};

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int shift = 0;
        while (m < n) {
            m >>= 1;
            n >>= 1;
            shift ++;
        }
        return m << shift;
    }
};

Another solution is to clear the rightmost 1 bit of n (apply the trick), until it is smaller or equal to m.

1
2
3
4
5
6
7
8
9

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        while (m < n) {
            n = n & (n - 1);
        }
        return m & n;
    }
};

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        while (m < n) {
            n = n & (n - 1);
        }
        return m & n;
    }
};

This approach is also O(1) in both time and space. This puzzle is one of those classic ones where we could apply those smart bit tweaks (twicks).

–EOF (The Ultimate Computing & Technology Blog) —