127.数字范围按位与

题目

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

示例 1：

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

输入：left = 0, right = 0 输出：0 示例 3：

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

思路

一段连续数字做按位与，最后只会留下它们二进制开头相同的部分，后面不同的部分全部变成 0。

class Solution {
    fun rangeBitwiseAnd(left: Int, right: Int): Int {
        // l 和 r 分别表示当前处理中的左边界和右边界
        var l = left
        var r = right

        // 记录一共右移了多少次
        // 因为最后要把共同前缀再左移回去
        var shift = 0

        // 只要 l 和 r 还不相等，
        // 说明它们的二进制后面还有不同的部分
        while (l < r) {
            // 两个数一起右移一位，相当于去掉最后一位
            l = l shr 1
            r = r shr 1

            // 记录去掉了几位
            shift++
        }

        // 循环结束时，l 和 r 已经相等
        // 这个相等的部分就是共同前缀
        // 后面被去掉的那些位，最后都应该补 0
        return l shl shift
    }
}

复杂度

• 时间复杂度:
• 空间复杂度:

• 下一题

• 邮箱 ：charon.chui@gmail.com
• Good Luck!