Leetcode 201 - Bitwise AND of Numbers Range（bit & math）

题意

给定两个数m和n，并且 m≤n ，求f(m, n) = m & (m + 1) & (m + 2) & ... & n的值。

思路

算法1

我们知道，在范围 [m,n] 内，对于二进制表示的第i位，只要这个范围内有一个数的第i位为0，那么我们结果 f(m,n) 的第i位就为0。

那么，如果m的第i位是1，并且之后 [m,n] 范围内的所有数第i位都是1，那么我们最后结果的第i位就是1了。

因为所以数是连续的，假设当前数是x，并且x的第i位是1。每次x增加1，对于第i位，如果能够保持是1，那么可以保持多少的长度呢？

如果当前第i位为1：

那么如果第i - 1到第0位都是0的话，那么可以保持的长度 l1=2i 个。

如果第i - 1位到第0位存在一些位为1的话，即我们之前已经取走了一部分，那么我们需要减去取走的部分 l2 （第i - 1位到第0位代表的数的值）。

最后可以保持的长度为： l=l1−l2 。

我们可以看一个例子：

4 3 2 1 0

0 0 0 0 0 0

0 0 0 0 1 1

0 0 0 1 0 2

0 0 0 1 1 3

0 0 1 0 0 4

0 0 1 0 1 5

0 0 1 1 0 6

0 0 1 1 1 7

0 1 0 0 0 8

…

观察可以发现：比如对于第2位，那么可以保持的长度为4。

并且对于我们的例子，数5对应的101，对于第2位， l1=4 ， l2=01=1 ，那么可以保持的长度 l=3 。由于我们的 n−m≤l ，所以第2位为1。

算法2

即求m和n的左边相同的部分。

证明待补。

代码

algorithm 1

class Solution { public: int rangeBitwiseAnd(int m, int n) { int count = n - m + 1, i = 0, res = 0; int x = m; while (x) { if (m & (1 << i)) { int cnt = 1 << i; int al = m & ((1 << i) - 1); cnt -= al; if (count <= cnt) res |= (1 << i); else res |= 0; } else { res |= 0; } x >>= 1; i++; } return res; } };

algorithm 2

class Solution { public: int rangeBitwiseAnd(int m, int n) { int cnt = 0; while (m != n) { m >>= 1; n >>= 1; cnt++; } return n << cnt; } };