Message290003
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 |
|
Date |
User |
Action |
Args |
2017-03-22 17:30:42 | niklasf | set | recipients:
+ niklasf, mark.dickinson |
2017-03-22 17:30:42 | niklasf | set | messageid: <1490203842.58.0.276315183014.issue29882@psf.upfronthosting.co.za> |
2017-03-22 17:30:42 | niklasf | link | issue29882 messages |
2017-03-22 17:30:42 | niklasf | create | |
|