201. Bitwise AND of Numbers Range

Posted on | Edited on | Views:

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

intuitive solutions: exceed the time limit

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        int res=0;
        for(int i=0;i<32;i++){
            int bitMask=(int)Math.pow(2,i);
            res=m&bitMask;
            for(int k=m+1;k<=n;k++){
                res&=k&bitMask;
            }
        }
        return res;
    }
}


Approach 1: Bit Shift
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        int shift=0;
        while(m<n){
            m>>=1;
            n>>=1;
            shift++;
        }
        return m<<shift;
    }
}

Approach 2: Brian Kernighan’s Algorithm (turn off the rightmost bit of one in a number)

1
2
3
4
5
6
7
8
9
class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        int shift=0;
        while(m<n){
            n&=n-1;
        }
        return m&n;
    }
}

0%