Bitwise AND of Numbers Range

描述

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.

分析

最简单的解法,遍历所有数,不断进行按位与,时间复杂度O(n)。这个做法太慢,不可接受。

先观察 [5,7]这个例子,5,6,7的二进制如下:

101
110
111

三个数按位与后结果为0,仔细观察这个过程我们可以得出,最后的结果是该范围内所有数的左边的共同部分,即公共左边首部(left header)。

我们再举一个更大的例子来感受一下,例如[26,30],这些数的二进制如下:

11010
11011
11100
11101
11110

最后的结果是11000,果然是公共左边首部。

发现了规律后,这题就简单了,我们只需要写代码找到公共左边首部即可。

解法1

// Bitwise AND of Numbers Range
// Time Complexity: O(log n), Space Complexity: O(1)
public class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        int mask = Integer.MAX_VALUE;

        while ((m & mask) != (n & mask)) {
            mask = mask << 1;
        }
        return m & mask;
    }
}

解法2

// Bitwise AND of Numbers Range
// Time Complexity: O(log n), Space Complexity: O(1)
public class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        while (n > m) {
            n &= n - 1;
        }
        return m & n;
    }
}

results matching ""

    No results matching ""