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 数字范围位相与的更多相关文章
-
[leetcode] Bitwise AND of Numbers Range
Bitwise AND of Numbers Range Given a range [m, n] where 0 <= m <= n <= 2147483647, return t ...
-
[LeetCode] 201. Bitwise AND of Numbers Range ☆☆☆(数字范围按位与)
https://leetcode.com/problems/bitwise-and-of-numbers-range/discuss/56729/Bit-operation-solution(JAVA ...
-
201 Bitwise AND of Numbers Range 数字范围按位与
给定范围 [m,n],其中 0 <= m <= n <= 2147483647,返回此范围内所有数字的按位与(包含m, n两端点).例如,给定范围 [5,7],您应该返回 4. 详见 ...
-
Leetcode201. Bitwise AND of Numbers Range数字范围按位与
给定范围 [m, n],其中 0 <= m <= n <= 2147483647,返回此范围内所有数字的按位与(包含 m, n 两端点). 示例 1: 输入: [5,7] 输出: 4 ...
-
LeetCode 201. 数字范围按位与(Bitwise AND of Numbers Range)
201. 数字范围按位与 201. Bitwise AND of Numbers Range 题目描述 给定范围 [m, n],其中 0 <= m <= n <= 214748364 ...
-
【LeetCode】201. Bitwise AND of Numbers Range 解题报告(Python)
[LeetCode]201. Bitwise AND of Numbers Range 解题报告(Python) 标签: LeetCode 题目地址:https://leetcode.com/prob ...
-
【LeetCode】201. Bitwise AND of Numbers Range
Bitwise AND of Numbers Range Given a range [m, n] where 0 <= m <= n <= 2147483647, return ...
-
LeetCode解题报告—— Number of Islands &; 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 ...
-
leetCode191/201/202/136 -Number of 1 Bits/Bitwise AND of Numbers Range/Happy Number/Single Number
一:Number of 1 Bits 题目: Write a function that takes an unsigned integer and returns the number of '1' ...
随机推荐
-
Python之路【第十七篇】Django进阶篇
规范 确立规范的好处: 代码可读性高 方便代码的定位极其查找 为以后代码扩容带来便利 场景: 在多个APP的场景下,单个app的URL函数功能较多的时候,我们可以通过以下方法来解决. 把Views写成 ...
-
ECShop出现Strict Standards: Only variables should be passed by reference in的解决方法
今天安装ecshop的时候最上面出现了一个错误提示:Strict Standards: Only variables should be passed by reference in F:\www.x ...
-
Python Queue实现生产与消费
Python Queue模块详解 from:https://blog.linuxeye.com/334.html Python中,队列是线程间最常用的交换数据的形式.Queue模块是提供队列操作的模块 ...
-
java中整数类型(short int long)的存储方式
在java中的整数类型有四种,分别是 byte short int long 其中byte只有一个字节 0或1,在此不详细讲解. 其他的三种类型如下: 1.基本类型:short 二进制位数:16包装 ...
-
一个基于集成jenkins的测试平台
(一)先看测试业务的情况: 有各种各样的任务包括代码构建.部署搭建.单元测试.功能自动化测试(包括许多模块的功能自动化测试,有十几个居多),性能测试.正确性验证:复杂一点的是这些任务在不同的测试阶段中 ...
-
linux基本命令-注销、关机、重起
链接地址:http://blog.163.com/bhao_home/blog/static/6647763120081202047945/ 一.注销,关机,重启 注销系统的logout命令 1,Lo ...
-
ruby简单的基本 3
类 Ruby一切都是对象,它包含了一个恒定.例如,可以使用.class物业查看对象的类型,你可以看一下1.class.你会发现常1类型是Fixnum,1但它是Fixnum的一个例子. Ruby本类cl ...
-
signapk
signapk工具可以实现对安卓ROM和安卓应用进行签名.在安卓DIY与安卓ROM制作中作用是非常大的.可以使用其对经过自己DIY修改美化后的应用进行签名或对制作好的安卓ROM卡刷包进行签名.让我们做 ...
-
【JavaFx教程】第二部分:Model 和 TableView
第二部分的主题 创建一个 模型 类. 在 ObservableList 使用模型类. 使用 Controllers 在 TableView 上显示数据. 创建 模型 类. 我们需要一个模型类来保存联系 ...
-
NativeXml: A native Delphi XML parser and writer
http://www.simdesign.nl/xml.html This software component contains a small-footprint Object Pascal (D ...