Woodstock Blog

a tech blog for general algorithmic interview questions

[LeetCode 201] Bitwise and of Numbers Range

Question

link

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.

Credits:
Special thanks to @amrsaqr for adding this problem and creating all test cases.

Show Tags
Bit Manipulation

Analysis

This is a pretty interesting mathematics question. Now we take 2 numbers as example:

Num1: 110010

Num2: 110111

Result: 110000

And:

Num1: 0110

Num2: 1100

Result: 0

Note that:

  1. if the first ‘1’ bit of the 2 numbers are at different position, the answer should simply be 0.

  2. if have same position, then the result would be the continous sequence of 1s, followed by all 0s.

Solution

The 2 best solutions is very well presented by Grandyang using bit shifting and masking. Please refer to code 1 and code 2 below.

I found a third solution at programcreek, which makes use of the fact that m is smaller than n.

Code

code 1

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

code 2

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

code 3

public int rangeBitwiseAnd(int m, int n) {
     while (n > m) {
          n = n & n - 1;
     }
     return m & n;
}