201

201. Bitwise AND of Numbers Range (Medium)

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

 

Example 1:

Input: left = 5, right = 7
Output: 4

Example 2:

Input: left = 0, right = 0
Output: 0

Example 3:

Input: left = 1, right = 2147483647
Output: 0

 

Constraints:

• 0 <= left <= right <= 231 - 1

Companies:
Amazon

Related Topics:
Bit Manipulation

Solution 1.

The answer is the common binary prefix between m and n.

// OJ: https://leetcode.com/problems/bitwise-and-of-numbers-range/
// Author: github.com/lzl124631x
// Time: O(C) where `C` is `log2(N)` (= 32 in this problem)
// Space: O(1)
class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int i = 0;
        while (m != n) {
            m >>= 1;
            n >>= 1;
            ++i;
        }
        return m << i;
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/bitwise-and-of-numbers-range/
// Author: github.com/lzl124631x
// Time: O(C) where `C` is `log2(N)` (= 32 in this problem)
// Space: O(1)
class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        while (m < n) n = n & (n - 1); // Keep removing the lowest bit of `n` until `m >= n`
        return n;
    }
};