Bitwise AND of Numbers Range

You have two integers m and n. You want the bitwise AND of all numbers from m to n.

Think about it this way. As m grows toward n, the range will contain both odd and even numbers. Odd numbers have their least significant bit set to 1. Even numbers have it set to 0. When you AND them together, that bit becomes 0.

In fact, whenever m and n are not equal, the bits where they differ will eventually become 0 in the final result. Only the common prefix of their binary representations can remain as 1 in the answer.

The solution shifts both numbers right until they match. Then it shifts back to restore the common prefix:

int rangeBitwiseAnd(int m, int n) {
    int f=0;
    while(m!=n) {
        m>>=1;
        n>>=1;
        ++f;
    }
    return m<<f;
}

This works because the differing bits in the range will produce zeros. Only the shared higher-order bits survive the AND operation across the entire range.

#bitwise