Leetcode:201 给定表示范围 [left, right] 的 left 和 right 两个整数，返回该范围内所有数字的按位与，包括

Question

为什么它失败了，我们是否可以在相同的逻辑中添加任何其他内容以使其正确。 它在左=6右=7处失败

这是代码片段：

类解决方案{ 公共静态 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);
    }
       
}

}

Answer 1

你的逻辑不正确；仅检查最高有效位是不够的。相反，如果端点的长度相同，您需要在端点的二进制表示形式中找到最长的匹配前缀。此外，可以使用

Integer.highestOneBit

实用方法来代替浮点数学。

public int rangeBitwiseAnd(int left, int right) {
    int leftHighest = Integer.highestOneBit(left), rightHighest = Integer.highestOneBit(right);
    if (leftHighest != rightHighest || left == 0 || right == 0) return 0;
    return leftHighest | rangeBitwiseAnd(left ^ leftHighest, right ^ leftHighest);
}