201. Bitwise AND of Numbers Range

201. Bitwise AND of Numbers Range (Medium)

Given a range [m, n] where 0 <= m <= n <= 2147483647, 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

Related Topics:
Bit Manipulation

Solution 1.

// OJ: https://leetcode.com/problems/bitwise-and-of-numbers-range/
// Author: github.com/lzl124631x
// Time: O(1)
// Space: O(1)
class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int ans = 0;
        for (int i = 0; i < 31; ++i) {
            int k = 1 << i, a = m / k, b = n / k;
            ans |= (a == b && a % 2) << i;
        }
        return ans;
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/bitwise-and-of-numbers-range/
// Author: github.com/lzl124631x
// Time: O(1)
// Space: O(1)
class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int count = 0;
        while (m && n && m != n) {
            m >>= 1;
            n >>= 1;
            ++count;
        }
        return m << count;
    }
};

Solution 3.

// OJ: https://leetcode.com/problems/bitwise-and-of-numbers-range/
// Author: github.com/lzl124631x
// Time: O(1)
// Space: O(1)
class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        while (m < n) n = n & (n - 1);
        return n;
    }
};