分别使用三种方式进行计算
- 转化为字符串，数‘1’ ，Python的原生库支持
- 引入 gmpy 库， 使用其中的popcount函数
- 优化的与运算
import gmpy
import time
# bin(n).count('1')
start =time.time()
sum = 0;
for i in range(1000000):
sum += bin(2**1024-1).count("1")
print "bin(n).count('1') :",time.time()-start
# gmpy.popcount(n)
start =time.time()
sum = 0;
for i in range(1000000):
sum += gmpy.popcount(2**1024-1)
print "gmpy.popcount(n) :",time.time()-start
# 一种优化的函数 numberOfSetBits
def numberOfSetBits(i):
i = i - ((i >> 1) & 0x55555555)
i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24
start =time.time()
sum = 0;
for i in range(1000000):
sum += numberOfSetBits(2**1024-1)
print "numberOfSetBits(call):",time.time()-start
# 去掉函数调用的影响
start =time.time()
sum = 0;
for a in range(1000000):
i = 2**1024-1
i = i - ((i >> 1) & 0x55555555)
i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
sum += (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24
print "numberOfSetBits :",time.time()-start
实际结果：
result.png
使用gmpy库的效率最高，若想更快，可以以空间换时间的设计更为快速的算法。
