leetcode 201 数字范围按位与

本文介绍: 给你两个整数 left 和 right ，表示区间 [left, right] ，返回此区间内所有数字按位与的结果（包含 left、right 端点）。（2）在区间 left到r i g ht中，因为是连续的整数，所以一定在left和r i g ht的后面的n位上均存在0，根据（1）可知后面的n位按位&的结果都是0.现在就可以看代码部分了，其中shift 表示的就是n。（1）假设区间中有w个数字，那么n个数字在第k位只要有一个数字不是1那么按位&的结果一定是0。本题是一个在思维上的方法，不涉及数据结构和具体的算法。

题目

给你两个整数 left 和 r i g ht ，表示区间 [left, ri g ht] ，返回此区间内所有数字按位与的结果（包含 left、ri g ht 端点）。
具体示例如下：

在这里插入图片描述

题解

本题是一个在思维上的方法，不涉及数据结构和具体的算法。
首先如果是暴力解法遍历区间内的所有数字是超过时间限制的。

首先有两个规则：
（1）假设区间中有w个数字，那么n个数字在第k位只要有一个数字不是1那么按位&的结果一定是0
（2）在区间left到ri g ht中，因为是连续的整数，所以一定在left和ri g ht的后面的n位上均存在0，根据（1）可知后面的n位按位&a mp;的结果都是0.
综上我们只需要找到n到底是几，以及le ft和ri g h t的公共前缀就可以了。现在就可以看代码部分了，其中shift表示的就是n。

代码

class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        int shift = 0;
        while(left!=right){
            left = left >> 1;
            right = right >> 1;
            shift+= 1;
        }
        return left << shift;
    }
};