Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive

Question

Why is it failing, Is there any other thing that we can add to the same logic to make it correct.

It fails at left=6 right=7

Here is the code snippet:

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);
        }
           
    }
}

Answer 1

Your logic is incorrect; it is not sufficient to only check the most significant bits. Instead, you need to find the longest matching prefix in the binary representation of the endpoints. In addition, the Integer.highestOneBit utility method can be used instead of floating-point math.

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);
}

Alternatively, an iterative solution:

public int rangeBitwiseAnd(int left, int right) {
    int res = 0;
    for (int i = 1 << 30; i > 0; i >>= 1) {
        int ltest = left & i;
        if (ltest != (right & i)) break;
        res |= ltest;
    }
    return res;
}