Bitwise AND of Numbers range

文章目录

给定一个范围[m,n]，0<=m<=n<=2147483647，求在这个范围内所有数的按位与。

比如范围是[5,7]，那么返回4。

当然最简单的解法就是对这个范围里的所有数都进行按位与，但很显然这样的解法效率很忙，而且做了许多不必要的计算，因为在这个范围内，只要有一位上的数是0的话，那么这个位的与就是0,不需要将范围中的数全部都计算一遍。

根据观察我们可以发现，如果一个数的二进制的位数比另一个要高，那么他们范围内的按位与肯定为0，比如15的二进制是1111，16的二进制是10000，将1111补全为01111，各位取与得到0。

根据这个思想，我们可以对第一位相同但之后不同的数字运用同样的思想。具体做法就是先将两个字符串s、t转化为二进制数，接着去找s和t中第一个不同的字符（就是0和1）的下标。下面的计算讲起来有点抽象，我举个例子就明白了：

s为101000110000101

t为101001100001101

根据上面的思想，可以得到最终的结果是在t的第六位结束的。而t是范围的终点，也就是说101001000000000是这个范围内的数。由于有这个数，第六位（包括第六位）之后的按位与都是0，那么最终结果就是第六位上一位的相同字符（第三位），即101000000000000。

整个解法的复杂度应该是O(logN+2^logN)，对两个整数转成二进制需要O(logN)，遍历二进制字符串的复杂度是O(2^logN)。