整数的位操作:判断整数的二进制是否含有至少两个连续的1

碰到一个利用字节位操作解决的问题,如何判断一个整数的二进制是否含有至少两个连续的1.

问题本身并不复杂,利用二进制的未操作即可完成,方法也有多种,不同方法效率也差很多,分别利用Python和C来实现并对比一下。

方法一:从头到尾遍历一遍每一位即可找出是否有连续的1存在

这个方法是最普遍的、第一感觉就能想到的方法,下面我们看一下它的具体实现:

Python代码:

上面的实现中,对于整数n先做取余运算(n % 2),如果余数为1,则n的最后一位是1,否则为0,并用this_is_one记录当前位;

然后判断一下,这次和上次的最后一位是不是都是1,如果是,则可以判定该整数有两个连续的1,否则把n向左移一位,继续循环开始的取余操作。

方法二:无需遍历每一位,但还是位操作:移一位(左移、右移皆可)然后和原数“位与”一下即可

这个原理不复杂,思考一下:

如果有两个连续的位为1,原数和移为后的数“位与”操作,就是会发生这两个连续的1进行“位与操作”,则结果中必出现至少一个位为1 (1&1 == 1),结果不为零;

如果没有至少两个连续的位为1,则1的两边都是0,原数和移为后的数“位与”操作,就是1与两边的0进行“位与操作”,则所有的1都变成了0 (1&0 == 0),结果必为零;

由以上推理,算法就简化的很多,只用一行代码即可搞定。

Python代码:

那么,上面两种方法的效率差多少呢,我们来测试一下看看:

Python代码

看一下运行结果,循环1百万次,方法二的速度是方法一的4倍多:

1000000 , time cost: 0.6687741279602051

1000000 , time cost: 0.16364359855651855

接下来,用C实现一下看看效率如何

C语言代码

编译并运行以上C代码:

从以上结果看,C语言实现的算法二比算法一块十几倍。

编译优化后运行:

编译器优化后的结果,算法二比算法一块4倍多,但都比未优化的快了很多。

顺便也“自黑”一下Python的性能,确实比起C来差很远。但是合适的工具做适合的事情永远是对的,不妨理解以下下面一段引文:

有个需要每天运行的Python程序,运行大概需要1.5秒。

我花了六小时用Rust重写它,现在运行需要0.06秒。

效率的提升意味着,我要花41年零24天,才能找回我多花的时间

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180914G08HL100?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券