一看到“数字范围按位与”这题,很多人第一反应是从 left 一路与到 right。
代码倒是好写,跑起来也很诚实,区间一大,直接超时。像 1 到 2147483647,你真去一位一位算,那不是做题,是磨机器。
这题我第一次看,就不太信“暴力枚举”能过。因为按位与有个很讨厌的特点:只要区间里某一位出现过一次 0,那这一位最后基本就保不住了。
比如 5~7:
一路与下来是 100,也就是 4。
你盯着这几个数多看两眼,就会发现一个规律:真正能保留下来的,不是某个具体数字,而是 left 和 right 的公共高位前缀。后面那些来回跳动的低位,进了区间之后,迟早会被与成 0。
所以这题没必要硬算整个区间,只要把 left 和 right 不同的那一段抹掉,剩下的就是答案。
先看一个比较顺手的写法:不断右移,直到两个数相等。右移了多少次,最后再左移回去。
classSolution{publicintrangeBitwiseAnd(int left, int right){int shift = 0;while (left < right) { left >>= 1; right >>= 1; shift++; }return left << shift; }}
这段代码不花,现场写也稳。
为什么对?因为右移的过程,本质上就是不断砍掉低位。什么时候 left 和 right 变成一样,说明它们高位前缀已经对齐了。那些被砍掉的低位,在原区间里一定发生过变化,保不住,补回去也只能补 0。
再说个更像位运算题的解法。
如果 right > left,那说明区间里至少有两个数。此时可以不断把 right 最右边的 1 清掉,直到 right <= left。因为这些低位的 1,在区间波动里也留不住。
classSolution{publicintrangeBitwiseAnd(int left, int right){while (left < right) { right = right & (right - 1); }return right; }}
这个写法更短,但面试时最好把思路讲清楚,不然容易写对了、解释虚了。
我自己更推荐第一种。不是因为它更快多少,而是因为不容易讲乱。算法题很多时候不是比谁能写出最炫的位运算,而是比谁下手稳,边界清楚。
这题的核心,不在“按位与”,而在“范围”两个字。只要有范围,低位就会抖;只要低位抖,最后大概率就是 0。真正值钱的,只剩那一截不会变的公共前缀。
题不难,想歪了就容易在循环里硬耗。这个坑,刷题时挺常见。