bit count or bit set && Python3

[Steven D'Aprano]

On Thu, 25 Oct 2012 09:17:40 -0700, rusi wrote:

> On Oct 25, 8:57 pm, Steven D'Aprano <steve
> +comp.lang.pyt... at pearwood.info> wrote:
>> On Fri, 26 Oct 2012 02:31:53 +1100, Chris Angelico wrote:
>> > On Fri, Oct 26, 2012 at 2:25 AM, Christian Heimes
>> > <christ... 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.
> 
> You meant 600% I think?

No, I mean a factor of 600 times faster. Look at the number of iterations 
used in each test: 10000 versus 100.

Using bin() and count() takes 0.6819710731506348/10000 = 6.8e-5 seconds 
on my computer; using MRAB's neat trick takes 4.141788959503174/100 = 
0.041 seconds. 0.041/6.8e-5 is slightly over 600.


-- 
Steven