题目描述#

哎呀，这题别被名字唬住——给你两个整数 left 和 right，表示一个区间 [left, right]（两端都算）。咱要返回的，是把这个区间里每一个整数全部 按位与 起来的结果。

举个例子，[5, 7] 就是 5 & 6 & 7。数字一多，挨个去与显然不现实，得找点规律。

思路#

咱第一眼看，按位与有个很"霸道"的脾气：只要参与运算的数里有任意一个在某一位上是 0，最终结果在这一位上就铁定是 0。所以问题就变成了——区间 [left, right] 里所有数，在哪些高位上是完全一致的？答案的本质，就是 left 和 right 这两个数二进制的公共前缀，前缀之后的低位全部补 0。

为啥是公共前缀？因为从 left 一路加到 right，低位一定经历过进位翻转，只要区间里某一位有变化，那一位上必然同时出现过 0 和 1，按位与就被抹成 0 了；只有那些从头到尾没变过的高位才能幸存下来。这就引出了两种写法。

解法一：右移找公共前缀。 咱让 left 和 right 一起右移，每移一位就用 cnt 记一笔，直到两者相等——这时它们对齐的部分就是公共前缀。最后把这个公共前缀再左移回 cnt 位，低位自动补上 0，就是答案。直观好懂，移了几位补几个零，账记得清清楚楚。

解法二：Brian Kernighan 抹低位。 本姑娘还有个更"耍帅"的写法：只要 right > left，就执行 right &= right - 1，这一步的作用是清除 right 二进制最低位的那个 1。不断抹掉 right 的低位 1，直到 right 缩小到不再大于 left，此刻的 right 恰好就是公共前缀对应的那个数。它跳过了"逐位移动"，直接奔着低位的 1 去消，往往循环次数更少，干净利落！

两种解法殊途同归，时间复杂度都是 $O(\log n)$ 级别（最多和位数挂钩），空间都是 $O(1)$。

知识边界#

• 按位与的"一票否决"：任一操作数在某位为 0，结果该位即为 0。本题答案 = left 与 right 的公共二进制前缀 + 低位补 0，根源就在这条性质。
• 公共前缀法（右移对齐）：同步右移 left、right 直到相等，记下移位次数 cnt，再左移回去补零。胜在直观。
• Brian Kernighan 技巧 x &= x - 1：每次清除 x 二进制最低位的 1，是统计 / 消除 set bit 的经典手法；这里用它快速把 right 削到公共前缀，循环次数只跟需要清掉的低位 1 个数有关——比逐位移动更省，但不那么直白，容易看懵哦。
• 循环条件 left < right：两者相等时说明已对齐到公共前缀，立即收工；若 left == right，区间只有一个数，直接返回它本身。

代码#

两版咱都原样保留。先是右移找公共前缀这版：

func rangeBitwiseAnd(left int, right int) int {
	cnt := 0
	for left < right {
		left >>= 1
		right >>= 1
		cnt++
	}
	return left << cnt
}

再来本姑娘偏爱的 Brian Kernighan 抹低位版，更短：

func rangeBitwiseAnd(left, right int) int {
    for left < right {
        right &= right - 1  // 清除 right 最低位的 1
    }
    return right
}

好啦，位运算章节又攒下一道～咱去整理今天的照片咯，下次再来收拾更刁钻的比特题！