# C/CPP soln, no loops/recursion

• ``````int Log2(int n) {
return log(n)/log(2);
}

int rangeBitwiseAnd(int m, int n) {
int diff;
// special case
if (m == n)
return m;

else {
diff = Log2(n-m) + 1;
m >>= diff;
n >>= diff;
return (m & n) << diff;

}

}``````

• Not sure but I guess this is the best approach. Thanks!

• not sure as the complexity of the function log is unknown

• http://stackoverflow.com/questions/17644958/binary-logarithm-in-o1-time-operating-on-registers-x86-or-simd-without-shift

It seems the binary log can be computed in constant time on x86, and there might be special instructions on x86 machines.

• Why is the (m&n) on the last step necessary? If the difference between the two already shifted out, wouldn't m << diff be sufficient?

• This post is deleted!

• That won't work. it has to be (m&n), because the difference is a conservative estimate. The difference tells us which bits would change, in the best case - i.e., if the difference between m and n is 1, then diff = 1. But this might not work if the difference caused more than 1 bit to flip.

For example, for [11,12], diff = 1, the difference would only shift the last bit. If we were to do m << diff or n << diff, we wouldn't account for the fact that 3 bits have flipped.

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