[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)!
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/680102.html