c/c++语言开发共享C++实现LeetCode(201.数字范围位相与)

[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.

for example, given the range [5, 7], you should return 4.

credits:
special thanks to  for adding this problem and creating all test cases.

又是一道考察位操作bit operation的题，相似的题目在leetcode中还真不少，比如repeated dna sequences 求重复的dna序列， single number 单独的数字,   single number ii 单独的数字之二 ， grey code 格雷码，和 reverse bits 翻转位 等等，那么这道题其实并不难，我们先从题目中给的例子来分析，[5, 7]里共有三个数字，分别写出它们的二进制为：

101　　110　　111

相与后的结果为100，仔细观察我们可以得出，最后的数是该数字范围内所有的数的左边共同的部分，如果上面那个例子不太明显，我们再来看一个范围[26, 30]，它们的二进制如下：

11010　　11011　　11100　　11101　　11110

发现了规律后，我们只要写代码找到左边公共的部分即可，我们可以从建立一个32位都是1的mask，然后每次向左移一位，比较m和n是否相同，不同再继续左移一位，直至相同，然后把m和mask相与就是最终结果，代码如下：

解法一：

  class solution {  public:      int rangebitwiseand(int m, int n) {          int d = int_max;          while ((m & d) != (n & d)) {              d <<= 1;          }          return m & d;      }  };

此题还有另一种解法，不需要用mask，直接平移m和n，每次向右移一位，直到m和n相等，记录下所有平移的次数i，然后再把m左移i位即为最终结果，代码如下：

解法二：

  class solution {  public:      int rangebitwiseand(int m, int n) {          int i = 0;          while (m != n) {              m >>= 1;              n >>= 1;              ++i;          }          return (m << i);      }  };

下面这种方法有点叼，就一行搞定了，通过递归来做的，如果n大于m，那么就对m和n分别除以2，并且调用递归函数，对结果再乘以2，一定要乘回来，不然就不对了，就举一个最简单的例子，m = 10, n = 11，注意这里是二进制表示的，然后各自除以2，都变成了1，调用递归返回1，这时候要乘以2，才能变回10，参见代码如下：

解法三：

  class solution {  public:      int rangebitwiseand(int m, int n) {          return (n > m) ? (rangebitwiseand(m / 2, n / 2) << 1) : m;      }  };  

下面这种方法也不错，也很简单，如果m小于n就进行循环，n与上n-1，那么为什么要这样与呢，举个简单的例子呗，110与上(110-1)，得到100，这不就相当于去掉最低位的1么，n就这样每次去掉最低位的1，如果小于等于m了，返回此时的n即可，参见代码如下：

解法四：

  class solution {  public:      int rangebitwiseand(int m, int n) {          while (m < n) n &= (n - 1);          return n;      }  };

参考资料：

到此这篇关于c++实现leetcode(201.数字范围位相与)的文章就介绍到这了,更多相关c++实现数字范围位相与内容请搜索<计算机技术网(www.ctvol.com)!!>以前的文章或继续浏览下面的相关文章希望大家以后多多支持<计算机技术网(www.ctvol.com)!!>！

需要了解更多c/c++开发分享C++实现LeetCode(201.数字范围位相与)，都可以关注C/C++技术分享栏目—计算机技术网(www.ctvol.com)!