数学方法 02

---

LeetCode 201

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

解题思路

一、位移

201题解1

原图出处

位移的思路就是找到，1.找到最大公共前缀，然后将前缀向左位移得最终答案

只要有一列是有一个0的，那么按位与运算后那一列一定是0，只有一列全是1才能保留下来，根据这个特性可以迭代循环，让 m 和 n 都向右位移，直到他们大值n比m小，说明找到最大公共前缀，在迭代期间记录下位移 shift 单位，最终结果再把前缀向左位移 shift 单位即可。

class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        int shift = 0;
        while (m < n) {
            m >>= 1;
            n >>= 1;
            shift++;
        }
        return n << shift;
    }
}

二、Brian Kernighan 算法

Brian Kernighan 算法关键在于 number 与 number-1 取按位与运算后得到结果其实就是让number最后边的1抹去成0。

201题解2

原图出处

让大值n循环与小1的 n-1 按位与，抹去最后面的1，直到比小值还小，说明最大前缀已经找到，可以直接返回n。

class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        while (m < n) {
            n = n & (n - 1);
        }
        return n;
    }
}

注意：循环里面不能让m = n，在样例[0,0]中，会一直卡在while里出不来，只需要保证n比m小退出来即可。