bit count or bit set && Python3

rusi rustompmody at gmail.com
Thu Oct 25 12:17:40 EDT 2012


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?



More information about the Python-list mailing list