范围按位与代码在left=6、right=7时出错，求原因及原逻辑修复方案

问题背景 #

给定区间[left, right]，求该区间内所有整数的按位与结果。现有Java代码在输入left=6、right=7时返回错误结果（原代码返回4，正确结果应为6），以下是具体分析和修正方案。

原代码：

class Solution {
    public static int log2(int N)
    {

        // calculate log2 N indirectly
        // using log() method
        int result = (int)(Math.log(N) / Math.log(2));

        return result;
    }
    public int rangeBitwiseAnd(int left, int right) {
        int res=1;
        int lower=log2(left);
        int higher = log2(right);
        // System.out.print(higher);
        if(left==right)
        return left;
        if(lower != higher){
            return left&(int)Math.pow(2,higher);
        }
        else{
            return (int)Math.pow(2,higher);
        }
           
    }
}

失效原因 #

1. 核心逻辑错误：原代码误以为当left和right最高位相同时，结果就是最高位对应的2的幂。但实际上，区间内所有数的按位与需要保留所有公共前缀位，而非仅最高位。比如6（二进制110）和7（111）的公共前缀是11，左移一位得到6，才是正确结果，而非4（100）。
2. log2方法的精度隐患：使用Math.log计算对数依赖浮点数运算，可能出现精度误差（比如某些数的计算结果会比实际小1），虽然这个案例中6和7的计算结果正确，但在其他场景下会出错。
3. 不同最高位时的逻辑冗余：当left和right最高位不同时，区间内必然包含一个最高位为higher的数和低于该位的数，按位与结果必然是0，但原代码用left & (int)Math.pow(2,higher)计算，虽然结果巧合正确，但逻辑不严谨。

修正方案 #

基于原代码“找最高位”的思路，我们可以通过以下修改修复问题：

修改后的代码 #

class Solution {
    public static int log2(int N) {
        // 改用位运算计算最高位位置，避免浮点数精度问题
        return N == 0 ? -1 : 31 - Integer.numberOfLeadingZeros(N);
    }
    
    public int rangeBitwiseAnd(int left, int right) {
        if (left == right) {
            return left;
        }
        
        int lower = log2(left);
        int higher = log2(right);
        
        if (lower != higher) {
            return 0; // 最高位不同，结果必为0
        } else {
            // 寻找left和right的公共前缀
            int shiftCount = 0;
            while (left != right) {
                left >>= 1;
                right >>= 1;
                shiftCount++;
            }
            // 将公共前缀左移还原
            return left << shiftCount;
        }
    }
}

关键修改说明 #

• 替换log2方法：用Integer.numberOfLeadingZeros计算最高位位置，这是Java中高效且准确的位运算方式，完全避免浮点数误差。
• 简化不同最高位的逻辑：直接返回0，逻辑更清晰，效率也更高。
• 修复相同最高位的逻辑：通过循环右移left和right，直到两者相等（此时得到公共前缀），再左移相同次数还原结果，这样就能得到区间内所有数的公共前缀，也就是按位与的正确结果。

测试left=6、right=7时：

• 6和7的最高位都是2，进入公共前缀查找逻辑。
• 右移一次后，left和right都变为3，循环结束。
• 将3左移1位得到6，与预期结果一致。

内容的提问来源于stack exchange，提问作者Abhishek