My solution by utilizing the pattern in the numbers


  • 0
    A

    The idea is simply. Calculate each bit individually. For each bit, the numbers appear periodically. The pattern is that a sequence of 1s is followed by a sequence of 0s. The number of 1s is the same as the number of 0s and the number is Math.pow(2, bitPosition). If the gap between m and n is larger than the number, we can be sure that there would be at least one 0 in this range. Otherwise, we only need to check the first bit and last bit in this range, if they are both 1, the bit in the result would also be one.

    public class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        int ret = 0;
        int gap = 0;
        int len = n - m + 1;
        for (int i = 0; i <= 31; i++){
            int mtail = m%2;
            int ntail = n%2;
            if((1 << i) < len){
                ret += 0;
            }
            else{
                if((mtail == ntail) && mtail == 1 ){
                    ret += (1<<i);
                }
            }
            m = (m >> 1);
            n = (n >> 1);
        }
        return ret;
    }
    

    }


Log in to reply
 

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