201.Bitwise AND of Numbers Range¶

201.Bitwise AND of Numbers Range¶

Tags: Medium Bit Manipulation

Links: https://leetcode.com/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.

Example 1:

Input: [5,7]
Output: 4

Example 2:

Input: [0,1]
Output: 0

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        unsigned int mask = INT_MAX;
        while ((m & mask) != (n & mask)) {
            mask <<= 1;
        }

        return mask & m;
    }
};

思路是去寻找左右边界从右向左第一个不同的位置，最后保留相同的部分即可。因为范围从m到n是连续的，那么它们的公共前缀部分设为xxx，则第一个不相同的位置肯定在n是1，在m里是0，不然违背大小关系。那么从m增长到n，则首先需要增长到xxx0111..11，然后增长到xxx100...00，然后再增长到n，那么很显然xxx0111..11和xxx100...00按位与，xxx后面的肯定都是0，那么也就意味着只需要求出m和n的相同二进制前缀即可。