C, Assembly, O(1), 2 lines

  • 0

    A bitwise AND of m and n gives only a partial answer, numbers in between m and n might still cause resetting of some of the other least significant bits (LSBs).

    Consider [5, 7] :

    5(101b) & 7(111b) = 101b

    Here the number 6 in the incrementing sequence would cause the LSB 0 to get reset. To figure this out, we need to find the first distinct MSB bit. In this case it's MSB 1.

    We know this bit would be set in the larger number ('n') only because LSBs to the right of this bit was reset at least once during this incrementing sequence. For example, we cannot reach 1011b without going through 1000b.

    Instead of a C loop, we could use an assembly instruction "bsrl" to figure out this MSB. Makes the code platform dependent, but it's an interesting approach.

    int rangeBitwiseAnd(int m, int n)
        int msb;
        __asm__("bsrl %1,%0" : "=r"(msb) : "r"(m ^ n)); // msb value is undefined if (m ^ n) == 0.
        return m == n ? m & n : m & n & ~((1 << msb) - 1); // handle (m == n) case

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.