LeetCode 30 days Challenge - Day 23

本系列将对LeetCode新推出的30天算法挑战进行总结记录，旨在记录学习成果、方便未来查阅，同时望为广大网友提供帮助。

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.

Example 1:

1 2	Input: [5,7] Output: 4

Example 2:

1 2	Input: [0,1] Output: 0

Solution

题目要求分析：给定一个整数m和一个整数n，m小于等于n，求将从n到m这些数的按位与的结果。

解法：

本题乍一看可以直接模拟，但是由于数字范围很大，模拟的开销太高，会TLE。

这里介绍一种做法：

首先观察：

0 0 0 0 0

1 0 0 0 1

2 0 0 1 0

3 0 0 1 1

4 0 1 0 0

5 0 1 0 1

6 0 1 1 0

7 0 1 1 1

8 1 0 0 0

这次0 - 8数字的二进制表示，可以看到，从右往左第 i 位的规律是：从0开始，0重复 2^i-1^ 次，1重复 2^i-1^ 次，一直这样循环下去。

再考虑与运算的特点：所有参加运算的数字中，出现了一个0，则结果就一定为0，这是显然的。

那么，问题转化为：如何判断m到n之间，每个比特位是否出现0？

从右往左，先确定当前循环节长度的一半：power = 1(2^0^)，每向左一位，power *= 2，注意不要爆INT。
确定循环节长度的一半后，对数字 k，k / power(2^i^)有以下情况：
1. 为奇数：那么k的二进制表示、从右往左第 i 位为 1；
2. 为偶数：那么k的二进制表示、从右往左第 i 位为 0；
有了以上的结论后，结合题目给出的m、n考虑，对第 i 位，m / power以及n / power 有以下情况：
1. 奇 + 奇，且为同一个奇数：m到n，第 i 位，全是 1，该位置需要记入结果，res += power；
2. 奇 + 奇，但为不同的奇数：m到n，第 i 位，两个1中间存在0，该位置不需要记入结果；
3. 奇 + 偶 / 偶 + 奇 /偶 + 偶：出现偶数，第 i 位存在 0，该位置不需要记入结果；

注：

注意while循环退出条件：当m小于power即可退出，因为m小于power，那么m表示为二进制表示后，power对应的那一位为0，不需要计入结果了。
注意power倍增不能爆INT，当power为2^30^次幂的时候，需要检测判断，并赋值为INT_MAX，直接乘2会导致爆INT：INT_MAX = 2^31^ - 1 < 2^31^

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        if (m == n) return m;
        int res = 0, power = 1;
        while (power <= m) {
            if ((m / power) % 2 != 0 && (m / power) == (n / power)) {
                res += power;
            }
            if (power == INT_MAX/2 + 1) power = INT_MAX;
            else power *= 2;
        }
        return res;
    }
};

传送门：Bitwise AND of Numbers Range

Karl

Karl's Nest

leetcode-day-23

LeetCode 30 days Challenge - Day 23

Bitwise AND of Numbers Range

Solution