New submission from Niklas Fiekas:
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
----------
components: Interpreter Core
messages: 290003
nosy: mark.dickinson, niklasf
priority: normal
severity: normal
status: open
title: Add an efficient popcount method for integers
type: enhancement
versions: Python 3.7
_______________________________________
Python tracker <rep...@bugs.python.org>
<http://bugs.python.org/issue29882>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
