作者 | 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倍多：
1000000 , time cost: 0.6687741279602051 1000000 , time cost: 0.16364359855651855
接下来，用C实现一下看看效率如何：
C语言代码：
#include #includeint 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 ms\n", 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++语言，从事网络爬虫、搜索引擎、自然语言理解处理等领域的研发工作。
閱讀更多 CSDN 的文章
