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

Question

代码图片=> 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')

Answer 1

我做了一些测试(Ubuntu 上的 Python 3.6):

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实现总能获胜。