Bit counting in Python

Python: ビットの数え上げ、そして実行時間計測のTips

integer または long integer 型の値のビットを数える方法。（Python らしいアプローチ）

・ビットの数え上げ => bin(x).count('1') イディオムを使う

>>> bin(0).count('1')
0
>>> bin(10).count('1')
2
>>> bin(2**81).count('1')
1
>>> bin(2**81-1).count('1')
81

・最左の'1'のビットの位置 => len(bin(x)) – 3　　※x>0 を前提とする

>>> len(bin(10)) - 3
3
>>> len(bin(2**81)) - 3
81
>>> len(bin(2**81-1)) - 3
80

・時間計測

>>> import timeit
>>> min(timeit.Timer("len(bin(2**81))-3").repeat(3))
0.7450731866756541
>>> min(timeit.Timer("len(bin(2**81-1))-3").repeat(3))
0.7362237379329599

参考：
http://jutememo.blogspot.com/2008/10/python_07.html