一行代码搞定整数二进制中的连续 1 判定!

百家 作者:CSDN 2018-09-23 11:53:51

作者 | veelion

责编 | 郭芮

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

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


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


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

Python代码:

def method_1(n) :                                                                                                               
    last_is_one = False
    this_is_one = False
    while n > 0:
        this_is_one = n % 2 
        if this_is_one and last_is_one:            return True
        n = n >> 1
        last_is_one = this_is_one    return False

上面的实现中,对于整数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代码:

def foo2(n):
    return (n & n< <1) > 0 

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

Python代码:

def test(func, loops):
    b = time.time()    for n in range(loops):
        func(n)
    e = time.time()
    print(loops, ', time cost:', e-b)if __name__ == '__main__':
    test(foo1, 10**6)
    test(foo2, 10**6)

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

< function method_1 at 0x7f60de787e18> 1000000 , time cost0.6687741279602051
< function method_2 at 0x7f60de75b598> 1000000 , time cost0.16364359855651855

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

C语言代码:

#include #include int method_1(int n) {  int last_is_one = 0;  int this_is_one = 0;  while(n > 0) {
    this_is_one = n % 2;    if(this_is_one && last_is_one) {      return 0;
    }
    n = n >> 1;
    last_is_one = this_is_one;
  }  return 1;
}int method_2(int n{  return n & n >> 1;
}void test(int (*func)(int), int loops) {  struct timeval b, e;
  gettimeofday(&b, 0);  for(int i = 0; i <  loops; i++) {
    (*func)(i);
  }
  gettimeofday(&e, 0);  double timecost = (e.tv_sec - b.tv_sec)*1000.0 + (e.tv_usec - b.tv_usec)/1000.0;                               
  printf("loops: %d, timecost: %f msn", loops, timecost);
}int main(int argc, char** argv{
  test(method_1, 1000000);
  test(method_2, 1000000);  return 0;
}

编译并运行以上C代码:

gcc two-consecutive-bits.c
./a.outloops: 1000000, timecost: 50.572000 msloops: 1000000, timecost: 4.253000 ms

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

编译优化后运行:

gcc two-consecutive-bits.c -O3
./a.outloops: 1000000, timecost: 13.407000 msloops: 1000000, timecost: 3.537000 ms

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

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

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

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

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

作者:veelion,具有十年开发经验,主要使用Python、C++语言,从事网络爬虫、搜索引擎、自然语言理解处理等领域的研发工作。

声明:本文为作者投稿,版权归对方所有。

关注公众号:拾黑(shiheibook)了解更多

[广告]赞助链接:

四季很好,只要有你,文娱排行榜:https://www.yaopaiming.com/
让资讯触达的更精准有趣:https://www.0xu.cn/

公众号 关注网络尖刀微信公众号
随时掌握互联网精彩
赞助链接