My O(1) solution using bitwise xor, and


  • 4
    L
    //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;
        }

  • 1
    H

    Could you provide some explanation?


  • 0
    L

    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.


Log in to reply
 

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