Bit counting in Python

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

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

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

1 2 3 4 5 6 7 8

>>> 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 を前提とする

1 2 3 4 5 6

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

・時間計測

1 2 3 4 5

>>> 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