Author niklasf
Recipients mark.dickinson, niklasf
Date 2017-03-22.17:30:42
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1490203842.58.0.276315183014.issue29882@psf.upfronthosting.co.za>
In-reply-to
Content
An efficient popcount (something equivalent to bin(a).count("1")) would
be useful for numerics, parsing binary formats, scientific applications
and others.

DESIGN DECISIONS

 * Is a popcount method useful enough?
 * How to handle negative values?
 * How should the method be named?

SURVEY

gmpy calls the operation popcount and returns -1/None for negative values:

>>> import gmpy2
>>> gmpy2.popcount(-10)
-1

>>> import gmpy
>>> gmpy.popcount(-10)

From the documentation [1]:

> If x < 0, the number of bits with value 1 is infinite
> so -1 is returned in that case.

(I am not a fan of the arbitrary return value).

The bitarray module has a count(value=True) method:

>>> from bitarray import bitarray
>>> bitarray(bin(123456789).strip("0b")).count()
16

Bitsets [2] exposes __len__.

There is an SSE4 POPCNT instruction. C compilers call the corresponding
intrinsic popcnt or popcount (with some prefix and suffix) and they
accept unsigned arguments.

Rust calls the operation count_ones [3]. Ones are counted in the binary
representation of the *absolute* value. (I propose to do the same).

Introducing popcount was previously considered here but closed for lack
of a PEP or patch: http://bugs.python.org/issue722647

Sensible names could be bit_count along the lines of the existing
bit_length or popcount for gmpy compability and to distinguish it more.

PERFORMANCE

$ ./python -m timeit "bin(123456789).count('1')"  # equivalent
1000000 loops, best of 5: 286 nsec per loop
$ ./python -m timeit "(123456789).bit_count()"  # fallback
5000000 loops, best of 5: 46.3 nsec per loop

[1] https://gmpy2.readthedocs.io/en/latest/mpz.html#mpz-functions
[2] https://pypi.python.org/pypi/bitsets/0.7.9
[3] https://doc.rust-lang.org/std/primitive.i64.html#method.count_ones
History
Date User Action Args
2017-03-22 17:30:42niklasfsetrecipients: + niklasf, mark.dickinson
2017-03-22 17:30:42niklasfsetmessageid: <1490203842.58.0.276315183014.issue29882@psf.upfronthosting.co.za>
2017-03-22 17:30:42niklasflinkissue29882 messages
2017-03-22 17:30:42niklasfcreate