Path: csiph.com!usenet.pasdenom.info!goblin1!goblin.stu.neva.ru!news2.euro.net!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <k6bsmh$qeg$1@dont-email.me>
References: <mailman.2846.1351176984.27098.python-list@python.org> <k6bsmh$qeg$1@dont-email.me>
From: Ian Kelly <ian.g.kelly@gmail.com>
Date: Thu, 25 Oct 2012 12:19:28 -0600
Subject: Re: bit count or bit set && Python3
To: Python <python-list@python.org>
Content-Type: text/plain; charset=ISO-8859-1
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.2859.1351189200.27098.python-list@python.org>
Lines: 50
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:32153

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