bit count or bit set && Python3

[Steven D'Aprano]

On Fri, 26 Oct 2012 02:31:53 +1100, Chris Angelico wrote:

> On Fri, Oct 26, 2012 at 2:25 AM, Christian Heimes <christian at python.org>
> wrote:
>> Simple, easy, faster than a Python loop but not very elegant:
>>
>>    bin(number).count("1")
> 
> Unlikely to be fast.

Oh I don't know about that. Here's some timing results using Python 2.7:

py> from timeit import Timer
py> t = Timer('bin(number).count("1")', setup='number=2**10001-1')
py> min(t.repeat(number=10000, repeat=7))
0.6819710731506348

Compare to MRAB's suggestion:

def count_set_bits(number):
     count = 0
     while number:
         count += 1
         number &= number - 1
     return count

py> t = Timer('count_set_bits(number)', 
...     setup='from __main__ import count_set_bits; number=2**10001-1')
py> min(t.repeat(number=100, repeat=7))
4.141788959503174


That makes the "inelegant" solution using bin() and count() about 600 
times faster than the mathematically clever solution using bitwise 
operations.

On the other hand, I'm guessing that PyPy would speed up MRAB's version 
significantly.



-- 
Steven