leetcode-201-数字范围按位与

题目描述:

给定范围 [m, n],其中 0 <= m <= n <= 2147483647,返回此范围内所有数字的按位与(包含 m, n 两端点)。

示例 1: 

输入: [5,7]
输出: 4

示例 2:

输入: [0,1]
输出: 0

要完成的函数:

int rangeBitwiseAnd(int m, int n) 

说明:

1、这道题给定两个int型整数,一个是开端,一个是末端,要求把开端和末端之间的数每一个都进行“与”操作,返回最后的结果。

2、这道题肯定不是直接做一个循环,每一个都去“与”一遍,这样子太费时间。我们要从数位的角度来考虑,因为数位只有32位,更加好操作。

如果只有两个数字,那么最后一位必然要改变,肯定一个是0,一个是1,那么与的结果肯定是0。

如果只有三个数字,那么最后一位和倒数第二位必然要改变,因为最后一位只能存储两个数字,三个数字的话必然倒数第二位也要改变,那么这时候倒数两个数字与的结果肯定是0。

如果有五个数字,那么最后一位、倒数第二位和倒数第三位必然要改变,因为最后两位只能存储四个数字,五个数字的话必然倒数第三位也要改变,所以最后三位与的结果肯定是0。

所以我们可以得出规律:

最后一位只能存储两个数,所以如果有三个数字,那么必然倒数第二位和最后一位为0。

倒数两位只能存储四个数,所以如果有五个数字,那么必然倒数三位都为0。

倒数三位只能存储八个数,所以如果有九个数字,那么必然倒数四位都为0。

……

所以我们可以根据给出来的开端和末端,计算出中间一共有多少个数,对应地找一下应该倒数几位都为0。

比如5是0101,7是0111,中间有三个数字5/6/7,那么必然倒数两位都是0,所以最终结果是0100。

这道题到这里看起来似乎是解决了,但其实我们只解决了其中一种情况。

还是上面这个例子,我们有三个数字,所以最后一位和倒数第二位都会改变,但是倒数第三位会不会改变呢?甚至倒数第四位会不会改变呢?

我们来看一下:

0100

0101

0110

0111

-------

1000

1001

如果从0100开始,到0110结束,三个数字,倒数两位是必须改变的,倒数第二位必须0和1都有出现,然后相与为0,但是倒数第三位,由于这个时候没有发生进位,所以没有影响,我们只需要考虑倒数两位的改变。

但是如果从0110开始,到1000结束呢,同样三个数字,同样的倒数两位必须改变,因为倒数两位的变化还是10->11->00,必然还是出现0和1,导致相与结果为0,但是这个时候前面几位却发生了进位,导致相与的结果不能是0100,而是0000。

这时候有一种很直觉的做法,就是把开端和末端两个数字“与”一下,接着再做上面的操作——找到倒数几位必须要改为0。

这种操作可以ac所有的测试样例,要解释的话也不难(不感兴趣原因的同学直接看代码啦),比如7和9

00111

01001

这两个是“跨域”的操作,三个数照理来说只有倒数两位要改变,前面的三位是不应该变化的(如果在同一个域中),由于倒数第二位产生了进位符号,传递给了倒数第三位,导致产生了前后两种不同的前三位的表示。开端和末端的前三位的表示可以代表两种不同的状态,并且所有中间值的前三位只有这两种状态,不应该再改变了。

这样解释可能比较难以理解,不懂的同学自己举一些需要“跨域”的例子,比如有三个数的,五个数的,甚至九个数的,多想想应该也就会比较清楚。

代码如下:(附详解)

    int rangeBitwiseAnd(int m, int n) 
    {
        if(m==n)return m;//边界情况,开端和末尾是同一个数,直接返回
        if(m==0)return 0;//边界情况,开端是0,相与必然为0,直接返回0
        int geshu=n-m,t=log10(geshu)/log10(2)+1,t1=t;//t表示倒数的几位要置零,t1记录一下t的值
        m=m&n;//开端“与”末尾,预防“跨域”的情况
        while(t--)//把倒数t位置零,先不断右移
            m>>=1;
        while(t1--)//再不断左移
            m<<=1;
        return m;//返回m
    }

上述代码实测24ms,beats 97.21% of cpp submissions。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能LeadAI

Python json 模块dumps、dump、loads、load的使用

本文主要讲下json.dumps和json.dump、json.loads和json.load的区别,因为经常需要加载json文件,读取数据,傻傻分不清...

981
来自专栏青玉伏案

iOS开发之Masonry框架源码解析

Masonry是iOS在控件布局中经常使用的一个轻量级框架,Masonry让NSLayoutConstraint使用起来更为简洁。Masonry简化了NSLay...

2068
来自专栏ACM算法日常

确定比赛名次(拓扑排序) - HDU 1285

这次先讲理论,因为拓扑排序在日常工作中用的并不多,甚至于很多人可能忘了计算机中存在这样一种排序。我大概的整理一下拓扑排序的定义和应用,以便看了这...

892
来自专栏数据结构与算法

BZOJ2115: [Wc2011] Xor(线性基)

第一行包含两个整数N和 M, 表示该无向图中点的数目与边的数目。 接下来M 行描述 M 条边,每行三个整数Si,Ti ,Di,表示 Si 与Ti之间存在 一条权...

661
来自专栏何俊林

如何学习OpenGL Shader开发?

shader也称着色器,着色器是运行在GPU上的小程序,着色器是一种C风格语言——GLSL。

2022
来自专栏AI科技大本营的专栏

入门 | 海量数据处理算法总结【超详解】

作者 | Angel_Kitty ➤1. Bloom Filter 【Bloom Filter】 Bloom Filter(BF)是一种空间效率很高的随机数据...

4219
来自专栏小狼的世界

Leetcode刷题记录:计算复数乘法

901
来自专栏恰同学骚年

剑指Offer面试题:29.丑数

  使用遍历法求第k个丑数,从1开始遍历,如果是丑数则count++,直到count=k为止。那么如何判断丑数呢?根据丑数的定义,丑数只有2,3,5这三个因子,...

722
来自专栏前端菜鸟变老鸟

判断两个json是不是相等的

1093
来自专栏函数式编程语言及工具

FunDA(13)- 示范:用户自定义操作函数 - user defined tasks

   FunDA是一种函数式的编程工具,它所产生的程序是由许多功能单一的细小函数组合而成,这些函数就是用户自定义操作函数了。我们在前面曾经提过FunDA的运作原...

1828

扫码关注云+社区