201. Bitwise AND of Numbers Range

發表於 | 分類於

problem

solution

option 1

不斷向右shift ，直到兩數字相等

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        // 5 = 0101
        // 7 = 0111
        int i=0;
        while(left != right){
            left>>=1;
            right>>=1;
            i++;
        }
        return right<<i;
    }
};

option 2

概念與option 1一樣，答案必定為2的指數

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        //      8   4   2   1
        //5     0   1   0   1
        //6     0   1   1   0
        //7     0   1   1   1
        
        while (right > left) {
              right&= (right-1);
         }
         return right;
    }
};

analysis

  • time complexity O(logn)
  • space complexity O(1)