bit count or bit set && Python3

[Ian Kelly]

On Thu, Oct 25, 2012 at 11:25 AM, Christian Gollwitzer <auriocus at gmx.de> wrote:
> There is a very geeky algorithm with only a few integer operations.
>
> Checkout
> http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSet64
>
> for a C version. Maybe the same thing is equally fast when ported to Python.

It does seem to be about five times faster than the loop, but still
only half as fast as the string-counting approach.  I'm using a 64-bit
CPU but only a 32-bit OS, but it probably doesn't make much difference
anyway for Python, which is going to do the computations with Python
longs rather than with 64-bit C integers.

Also, this approach is a bit limited in that it only works for 32-bit
ints, so you can't pass it an aribtrary precision int and expect
correct results.

By the way, I expect the reason that Steve saw a 600x difference and
I'm only getting a 10x difference is because he was testing 10000-bit
ints with expensive "long" operations, whereas I'm using 32-bit ints
that aren't too far removed from the C level.


>>> from timeit import Timer
>>> t = Timer("bin(number).count('1')", setup="number=2**31-1")
>>> min(t.repeat(number=1000000, repeat=7))
0.6388884620810749
>>> def count_set_bits(number):
...   count = 0
...   while number:
...     count += 1
...     number &= number - 1
...   return count
...
>>> t = Timer("count_set_bits(number)", setup="from __main__ import count_set_bi
ts; number = 2 ** 31-1")
>>> min(t.repeat(number=100000, repeat=7))
0.5898140685478239
>>> def count_set_bits_geeky(number):
...     c = ((number & 0xfff) * 0x1001001001001 & 0x84210842108421) % 0x1f
...     c += (((number & 0xfff000) >> 12) * 0x1001001001001 & 0x84210842108421)
% 0x1f
...     c += ((number >> 24) * 0x1001001001001 & 0x84210842108421) % 0x1f
...     return c
...
>>> t = Timer("count_set_bits_geeky(number)", setup="from __main__ import count_
set_bits_geeky; number = 2 ** 31-1")
>>> min(t.repeat(number=100000, repeat=7))
0.1247119396459766