时间戳

首页 > 解决方案 > 为什么 bin(x).count('1') 比 x &= x-1 快？

python - 为什么 bin(x).count('1') 比 x &= x-1 快？

问题描述

代码图片=> https://i.imgur.com/KZUzckt.png

该算法用于计算二进制数中设置位（位等于 1）的数量。

我认为按位运算会更快，因为将数字转换为字符串然后计算 '1' 听起来要慢得多。 

def counting1(num):
    count = 0
    while num:
         num &= num-1
         count += 1
    return count   

def counting2(num):
    return bin(num).count('1')

标签： pythonstringalgorithmcountbinary

解决方案

我做了一些测试（Python 3.6在 Ubuntu 上）：

import timeit

for n in [0, 1, 2, 20, 21, 22, 23, 24, 25, 26, 27, 53, 100, 500, 10**5, 10**10, 10**50]:
    assert counting_1(n) == counting_2(n)
    t1 = timeit.timeit('f(n)', 'from __main__ import counting_1 as f, n')
    t2 = timeit.timeit('f(n)', 'from __main__ import counting_2 as f, n')
    print('{:10.4f} {:10.4f} | best {} | n {}'.format(
        t1,
        t2,
        '1' if t1 < t2 else '2',
        n))

结果是：

0.0930     0.2469 | best 1 | n 0
0.1616     0.2590 | best 1 | n 1
0.1655     0.2606 | best 1 | n 2
0.2320     0.2682 | best 1 | n 20
0.2929     0.2663 | best 2 | n 21
0.2934     0.2681 | best 2 | n 22
0.3715     0.2696 | best 2 | n 23
0.2331     0.2670 | best 1 | n 24
0.2939     0.2680 | best 2 | n 25
0.2915     0.2663 | best 2 | n 26
0.3766     0.2738 | best 2 | n 27
0.3723     0.2684 | best 2 | n 53
0.2926     0.2692 | best 2 | n 100
0.5247     0.2739 | best 2 | n 500
0.5335     0.2935 | best 2 | n 100000
0.9223     0.3147 | best 2 | n 10000000000
4.4814     0.5307 | best 2 | n 100000000000000000000000000000000000000000000000000

速度差异可能与内置类在 C 中实现并且通常优于纯 python 解决方案这一事实有关。

对于小数字counting_1()更快，可能是因为在counting_2();中转换数字的开销。但显然对于大量的这种开销是微不足道的。

注意：实际持续时间取决于1存在的数量，在我的测试中，对于 20 到 30 之间的数字，这两个函数非常相似，但对于更大的数字，原生 C 实现总是获胜。

推荐阅读