返回

[Leetcode]201. Bitwise AND of Numbers Range(C++)

题目描述

题目链接:201. Bitwise AND of Numbers Range

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

例子

例子 1

Input:left = 5, right = 7 Output:4

例子 2

Input:left = 0, right = 0 Output:0

例子 3

Input:left = 1, right = 2147483647 Output:0

Constraints

  • 0 <= left <= right <= 2^31 - 1

解题思路

这道题如果直接遍历 range 的所有数字进行相与会超时,因此我们需要找规律。实际上这道题的结果的最大位数是31,因此只需要判断这 31 位里面有哪几位为 1 即可。也就是判断 range 只要其中一位为 0 那么那一位一定为 0.而从数的连续性我们可以知道,以 5 (二进制为 101)到 10 (二进制为 1010)为例,只要看最大数的最高位即可,最高位往左全都是 0,最高位往右也肯定会有 0(因为数的连续性),如果 leftright 的最高位都为 1 (比如10和8),那么结果则为该位对应的数字,否则是 0。

代码如下:

class Solution {
public:
    int rangeBitwiseAnd(int left, int right) {
        int ret = 0;
        for (int i = 30; i >= 0; --i) {
            int mask = (1 << i);
            if ((right & mask) > 0) {
                if ((left & mask) > 0) {
                    ret ^= (1 << i);
                } else {
                    break;
                }
            }
        }
        return ret;
    }
};
  • 时间复杂度: O(1)
  • 空间复杂度: O(1)

GitHub 代码同步地址: 201.BitwiseAndOfNumbersRange.cpp

其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions

Built with Hugo
Theme Stack designed by Jimmy