Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #32153

Re: bit count or bit set && Python3

Show all headers | View raw

On Thu, Oct 25, 2012 at 11:25 AM, Christian Gollwitzer <auriocus@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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

bit count or bit set && Python3 Charles Hixson <charleshixsn@earthlink.net> - 2012-10-25 07:47 -0700
  Re: bit count or bit set && Python3 rusi <rustompmody@gmail.com> - 2012-10-25 09:13 -0700
    Re: bit count or bit set && Python3 Terry Reedy <tjreedy@udel.edu> - 2012-10-25 16:16 -0400
  Re: bit count or bit set && Python3 Christian Gollwitzer <auriocus@gmx.de> - 2012-10-25 19:25 +0200
    Re: bit count or bit set && Python3 Ian Kelly <ian.g.kelly@gmail.com> - 2012-10-25 12:19 -0600
  Re: bit count or bit set && Python3 casevh@gmail.com - 2012-10-26 08:42 -0700
    Re: bit count or bit set && Python3 Charles Hixson <charleshixsn@earthlink.net> - 2012-10-26 09:30 -0700
  Re: bit count or bit set && Python3 casevh@gmail.com - 2012-10-26 08:42 -0700

csiph-web