题目

给你两个整数 left 和 right ，表示区间 [left, right] ，返回此区间内所有数字 按位与 的结果（包含 left 、right 端点）。

示例 1：

1 2	输入：left = 5, right = 7 输出：4

示例 2：

1 2	输入：left = 0, right = 0 输出：0

示例 3：

1 2	输入：left = 1, right = 2147483647 输出：0

提示：

0 <= left <= right <= 2^31 - 1

解题

这道题如果按照迭代区间的每一个元素，然后按位进行与运算，会超时。因此需要优化。

我们观察发现，将每个数字用二进制表示后对齐，逐位遍历比特位上的值，只要某一列上出现一个0，那么与运算之后的结果在该位上也一定是0。

因此，这个问题就转换为：给定两个整数，找到它们对应的二进制字符串的公共前缀，然后将剩余位补零。

在实际编码中，我们让两个数字不断右移，直到相等，就得到了公共前缀，此时再左移补零。

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int k = 0;
        while(left != right) {
            k++;
            left >>= 1;
            right >>= 1;
        }
        return left << k;
    }
}