[LeetCode] Bitwise AND of Numbers Range 数字范围位相与

时间:2021-11-25 22:42:51

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.

又是一道考察位操作Bit Operation的题,相似的题目在LeetCode中还真不少,比如Repeated DNA Sequences 求重复的DNA序列Single Number 单独的数字,  Single Number II 单独的数字之二 ,Grey Code 格雷码,和Reverse Bits 翻转位 等等,那么这道题其实并不难,我们先从题目中给的例子来分析,[5, 7]里共有三个数字,分别写出它们的二进制为:

101  110  111

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

010  011  100  101  110

发现了规律后,我们只要写代码找到左边公共的部分即可,我们可以从建立一个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 <<= ;
}
return m & d;
}
};

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

解法二:

class Solution {
public:
int rangeBitwiseAnd(int m, int n) {
int i = ;
while (m != n) {
m >>= ;
n >>= ;
++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 / , n / ) << ) : 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 - );
return n;
}
};

参考资料:

https://discuss.leetcode.com/topic/13508/one-line-c-solution

https://discuss.leetcode.com/topic/12133/bit-operation-solution-java

https://discuss.leetcode.com/topic/20176/2-line-solution-with-detailed-explanation

LeetCode All in One 题目讲解汇总(持续更新中...)

[LeetCode] Bitwise AND of Numbers Range 数字范围位相与的更多相关文章

  1. &lbrack;leetcode&rsqb; Bitwise AND of Numbers Range

    Bitwise AND of Numbers Range Given a range [m, n] where 0 <= m <= n <= 2147483647, return t ...

  2. &lbrack;LeetCode&rsqb; 201&period; Bitwise AND of Numbers Range &star;&star;&star;&lpar;数字范围按位与&rpar;

    https://leetcode.com/problems/bitwise-and-of-numbers-range/discuss/56729/Bit-operation-solution(JAVA ...

  3. 201 Bitwise AND of Numbers Range 数字范围按位与

    给定范围 [m,n],其中 0 <= m <= n <= 2147483647,返回此范围内所有数字的按位与(包含m, n两端点).例如,给定范围 [5,7],您应该返回 4. 详见 ...

  4. Leetcode201&period; Bitwise AND of Numbers Range数字范围按位与

    给定范围 [m, n],其中 0 <= m <= n <= 2147483647,返回此范围内所有数字的按位与(包含 m, n 两端点). 示例 1: 输入: [5,7] 输出: 4 ...

  5. LeetCode 201&period; 数字范围按位与&lpar;Bitwise AND of Numbers Range&rpar;

    201. 数字范围按位与 201. Bitwise AND of Numbers Range 题目描述 给定范围 [m, n],其中 0 <= m <= n <= 214748364 ...

  6. 【LeetCode】201&period; Bitwise AND of Numbers Range 解题报告(Python)

    [LeetCode]201. Bitwise AND of Numbers Range 解题报告(Python) 标签: LeetCode 题目地址:https://leetcode.com/prob ...

  7. 【LeetCode】201&period; Bitwise AND of Numbers Range

    Bitwise AND of Numbers Range  Given a range [m, n] where 0 <= m <= n <= 2147483647, return ...

  8. LeetCode解题报告—— Number of Islands &amp&semi; Bitwise AND of Numbers Range

    1. Number of Islands Given a 2d grid map of '1's (land) and '0's (water), count the number of island ...

  9. leetCode191&sol;201&sol;202&sol;136 -Number of 1 Bits&sol;Bitwise AND of Numbers Range&sol;Happy Number&sol;Single Number

    一:Number of 1 Bits 题目: Write a function that takes an unsigned integer and returns the number of '1' ...

随机推荐

  1. Python之路【第十七篇】Django进阶篇

    规范 确立规范的好处: 代码可读性高 方便代码的定位极其查找 为以后代码扩容带来便利 场景: 在多个APP的场景下,单个app的URL函数功能较多的时候,我们可以通过以下方法来解决. 把Views写成 ...

  2. ECShop出现Strict Standards&colon; Only variables should be passed by reference in的解决方法

    今天安装ecshop的时候最上面出现了一个错误提示:Strict Standards: Only variables should be passed by reference in F:\www.x ...

  3. Python Queue实现生产与消费

    Python Queue模块详解 from:https://blog.linuxeye.com/334.html Python中,队列是线程间最常用的交换数据的形式.Queue模块是提供队列操作的模块 ...

  4. java中整数类型(short int long)的存储方式

    在java中的整数类型有四种,分别是 byte  short int long 其中byte只有一个字节 0或1,在此不详细讲解. 其他的三种类型如下: 1.基本类型:short 二进制位数:16包装 ...

  5. 一个基于集成jenkins的测试平台

    (一)先看测试业务的情况: 有各种各样的任务包括代码构建.部署搭建.单元测试.功能自动化测试(包括许多模块的功能自动化测试,有十几个居多),性能测试.正确性验证:复杂一点的是这些任务在不同的测试阶段中 ...

  6. linux基本命令-注销、关机、重起

    链接地址:http://blog.163.com/bhao_home/blog/static/6647763120081202047945/ 一.注销,关机,重启 注销系统的logout命令 1,Lo ...

  7. ruby简单的基本 3

    类 Ruby一切都是对象,它包含了一个恒定.例如,可以使用.class物业查看对象的类型,你可以看一下1.class.你会发现常1类型是Fixnum,1但它是Fixnum的一个例子. Ruby本类cl ...

  8. signapk

    signapk工具可以实现对安卓ROM和安卓应用进行签名.在安卓DIY与安卓ROM制作中作用是非常大的.可以使用其对经过自己DIY修改美化后的应用进行签名或对制作好的安卓ROM卡刷包进行签名.让我们做 ...

  9. 【JavaFx教程】第二部分:Model 和 TableView

    第二部分的主题 创建一个 模型 类. 在 ObservableList 使用模型类. 使用 Controllers 在 TableView 上显示数据. 创建 模型 类. 我们需要一个模型类来保存联系 ...

  10. NativeXml&colon; A native Delphi XML parser and writer

    http://www.simdesign.nl/xml.html This software component contains a small-footprint Object Pascal (D ...