【原】LeetCode刷题实战201：数字范围按位与

程序IT圈 2021-03-05

展开全文

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 数字范围按位与，我们先来看题面：

https:///problems/bitwise-and-of-numbers-range/

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

题意

给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。

示例

示例 1:

输入: [5,7]
输出: 4

示例 2:

输入: [0,1]
输出: 0

解题

思路一：当一个数+1时，总会有这么一个规律“某一位后的数字，全部被置为相反数”。

举个例子：

010111 + 1 = 011000，则010111 & 011000 = 010000。那么，x & (x+1) 后几位相反数的“与操作”，结果总为0。

所以，当(m,m+1,...n-1,n)进行连续“与操作”时，会按照上述规律被抵消很大一部分，而只剩下n的前缀部分，最后只需将n归位。举个例子：

m = 5(0101), n = 7 (0111)。不停右移，得到n前缀部分为01，最后归位前缀得res=0100=4

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

思路二：从高位向低位与，利用 n&(n-1)的特性：n & (n - 1) 可以将 n 最右边的 1 变成 0

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