201. Bitwise AND of Numbers Range

https://leetcode.com/problems/bitwise-and-of-numbers-range/

Solution:

We need to find a way to reduce the time complexity. As indicated by the title, bitwise operation may be a choice. One way is to check the 1s and 0s at each bit (31 bits in total). For each bit, once 0 is found, then the final results at that bit will be 0 (bitwise AND).

But this still is not enough. Actually once the number on the higher edge has one bit that is 1 on the higher bits more than that of the lower edge, then all the bits will become 0 from AND. So we just need to find the locations of the highest bit that is 1 for both m and n. If the location of n is higher than that of m, the result will be 0. (we can also work on the lower side to figure out the highest location for the non-zero bits for both numbers, then the iteration can start from that bit to higher once. But for simplicity, I just set the out-layer loop starting from 0.)

One detail, when n is the INT_MAX, we cannot use it as the end condition for the for-loop (since it will trigger INT_MAX + 1). However, the good new is that INT_MAX itself has no constrain on AND at all. So once n is the maximum, we just need to set it to be INT_MAX - 1.

Code:

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        if(n==INT_MAX) n = n-1;
        int res = 0;
        int l1 = 30, l2 = l1;// l1 is the highest "1" bit location for m; 
        while(l1>=0){
            if((1<<l1)&m) break;
            --l1;
        }
        while(l2>=0){// similar for l2 to n;
        if((1<<l2)&n) break;
            --l2;
        }
        if(l2>l1) return 0;
        for(int i=0; i<=l1; ++i){
            int t = (1<<i);
            for(int j=m; j<=n; ++j){
                t = t & j;
                if(!t) break;
            }
            res |= t;
        }
        return res;
    }
};