//34ms
int rangeBitwiseAnd(int m, int n) {
int xmask = m ^ n;
int mlen = 0;
int mask;
if ((xmask >> (mlen + 16)) > 0) mlen += 16;
if ((xmask >> (mlen + 8)) > 0) mlen += 8;
if ((xmask >> (mlen + 4)) > 0) mlen += 4;
if ((xmask >> (mlen + 2)) > 0) mlen += 2;
if ((xmask >> (mlen + 1)) > 0) mlen ++;
mask = ~0 << mlen;
return m & mask;
}
My O(1) solution using bitwise xor, and


let's assume that m < n, so there must be a bit that m = xxxx0yyyyy and n = xxxx1zzzzz, where the x part are the same and the y/z part can be anything.
The goal of this problem is to calculate all the bitwise and of the numbers between m and n, which must include k = xxxx100000, so obviously the answer must be xxxx000000.
The xmask extracts the x part out, so we just need to count the position of highest 1 of xmask and calculate the answer accordingly.