LeetCode: 201. 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

解题思路

记 m = AX, n=AY，则， m 到 n 的所有数字高位都是 A。而 X， Y 的最高位(由于 m <= n) 分别是 0, 1。 因此，m 到 n 的低位中， X，Y 的所有数字都出现了,这些数按位相与为 0。m&(m-1)...(n-1)n = AO(其中，O为低位的 0)。

AC 代码

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int cnt = 0;

        while(m != n) 
        {
            m >>= 1;
            n >>= 1;
            ++cnt;
        }

        return (m << cnt);
    }
};