☆打卡算法☆LeetCode 201. 数字范围按位与 算法解析

theme: arknights

携手创作，共同成长！这是我参与「掘金日新计划 · 8 月更文挑战」的第20天，点击查看活动详情

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定两个整数表示区间，返回此区间内所有数字按位与的结果。”

题目链接：

来源：力扣（LeetCode）

链接： 201. 数字范围按位与 - 力扣（LeetCode）

2、题目描述

给你两个整数 left 和 right ，表示区间 [left, right] ，返回此区间内所有数字 按位与 的结果（包含 left 、right 端点）。

示例 1：
输入： left = 5, right = 7
输出： 4

示例 2：
输入： left = 0, right = 0
输出： 0

二、解题

1、思路分析

首先来了解一下什么是按位与。

按位与的运算规则：

• 0 & 0 = 0
• 0 & 1 = 1 & 0 = 0
• 1 & 1 = 1

总结一下就是按位与的两头的值都为1，按位与的结果才是1，否则都是0。

那么，根据这个性质，只要这一系列中有一个数为0，则这一系列按位与运算都为0。

即使在最极端的情况下，剩余部分中每一位也一定存在 0 ，因此我们可以认定，剩余部分按位与结果一定为 0。

回到本题，首先，可以对范围内的每个数字用二进制的字符串表示，然后将每个二进制字符串的位置对齐，比如：

可以发现，对所有数字执行按位与运算的结果是所有对应二进制字符串的公众前缀再用零补充剩余位的操作。

那么是否就可以采用位移操作，将两个数字不断的向右移动柜，直到数字相等，即数字缩减为它们的公共前缀，然后将公共前缀向左移动，将零添加到公众前缀的右边获得最后的结果。

2、代码实现

代码参考：

class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        int shift = 0;
        // 找到公共前缀
        while (m < n) {
            m >>= 1;
            n >>= 1;
            ++shift;
        }
        return m << shift;
    }
}

3、时间复杂度

时间复杂度：O(log n)

算法的时间复杂度取决于m和n的二进制位数，由于m≤n，因此时间复杂度为n的二进制位数。

空间复杂度：O(1)

只需要常数级的变量空间。

三、总结

总结一下，算法由两部分组成：

• 1、右移操作，将两个数字压缩为它们的公共前缀。
• 2、左移操作，将得到的公共前缀左移相同的操作数，后面再补领得到结果。