201 - Bitwise AND of Numbers Range

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.
For example, given the range [5, 7], you should return 4.
Credits:
Special thanks to @amrsaqr for adding this problem and creating all test cases.
Hide Tags
Bit Manipulation

在纸上比划了一下：
-- 如果两个数字开始的 bit 1 不是同一个 bit 位，结果铁定是 0，因为中间包含了 2 的整数次方。
-- 如果开始在同一个 bit 位，就要看两个数字的共同 bit 1 有几位，这几位组成的数字就是结果了。

转换一下逻辑：
同步扫描两个数字的同一个 bit 位，
-- 如果两个数字的 bit 位不同，则就此结束，返回已经统计好的结果即可。
-- 如果相同，则进行统计，只需要每次加上（准确说应该是 或上）任一个数字跟 mask 与的结果即可。
剪枝：起点为 0 结果为0；两数相同直接返回原值。

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int rst=0;
        if(m)
        {
            if(m==n)
                return m;
   
            for(int ii=31; ii>0; ii--)
            {
                int mask = (1<<ii), nmask = n&mask, mmask = m&mask;

                if(nmask != mmask)
                    return rst;
               
                rst += nmask;
            }
        }
        return rst;
    }
};
64 ms.

仔细再想这道题的实质，那就是，看着两个数字，从最高位开始，有多少相同的 bit 位，直到出现不同的 bit 位。
无论在这个不同的 bit 位出现之前是 0 还是 1，只要相同就行，这部分也就是最后的结果。
从二进制不断增长的过程也可以印证这个结论：一旦产生进位，相同的部分只可能是全 0，其余情况则高位向下某些部分保持不变。

So，关键是，值不同的 bit 位。。。想到什么了么。。。？是的，异或。
所以可以有这样的解法：
  1. 首先对两数字求异或，那么 bit 位不同的就会被 1 标识出来；
  2. 然后将第一个 1 之后的所有 bit 位“涂抹”成 1 ，可以看成，从第一个不同的 bit 位，其后的所有 bit 都被标识为 “丢弃”；
  3. 再讲这个涂抹之后的数字求反，所有被丢弃的 bit 就全是 0，而之前的 bit 就全是 1 了；
  4. 用这个数字做掩码，去跟任意一个与以下（无所谓哪一个，因为从第一个不同的 bit 开始都会被丢弃），就可以得到需要的结果了。

讨论区里有这个思路的实现：

Whenever a bit changes when counting from m to n, that bit will be 0 in the AND of the range. So we consider the XOR x of m and n. The leftmost 1 bit in x is the last bit that changes at some point when counting from m to n. This bit and the bits to the right of it are all 0 in the AND of the range. We can easily fill all the bits to the right of that bit with 1s using the OR operations below to create a mask. This technique "smears" the 1 bits in x to the right. Then it's just a matter of returning the rest of m excluding those bits (the bits in m that did not change when counting up to n), which is precisely the AND of the range from m to n.

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        unsigned int x = m ^ n;
        x |= x >> 1, x |= x >> 2, x |= x >> 4, x |= x >> 8, x |= x >> 16;
        return m & ~x;  
    }
};

以前就见过他玩这一套，这哥们好像很喜欢涂抹，哈哈。