[issue29882] Add an efficient popcount method for integers

Mark Dickinson added the comment: New changeset 83a0ef2162aa379071e243f1b696aa6814edcd2a by Mark Dickinson in branch 'main': bpo-29882: Fix portability bug introduced in GH-30774 (#30794) https://github.com/python/cpython/commit/83a0ef2162aa379071e243f1b696aa6814edcd2a -- _

[issue29882] Add an efficient popcount method for integers

Change by Mark Dickinson : -- pull_requests: +28979 pull_request: https://github.com/python/cpython/pull/30794 ___ Python tracker ___ __

[issue29882] Add an efficient popcount method for integers

STINNER Victor added the comment: New changeset cd8de40b3b10311de2db7b90abdf80af9e35535f by Victor Stinner in branch 'main': bpo-29882: _Py_popcount32() doesn't need 64x64 multiply (GH-30774) https://github.com/python/cpython/commit/cd8de40b3b10311de2db7b90abdf80af9e35535f -- _

[issue29882] Add an efficient popcount method for integers

Change by STINNER Victor : -- pull_requests: +28959 pull_request: https://github.com/python/cpython/pull/30774 ___ Python tracker ___ __

[issue29882] Add an efficient popcount method for integers

Vedran Čačić added the comment: Well, bit_sum is what it really is. But I agree it's a terrible name. :-) -- nosy: +veky ___ Python tracker ___

[issue29882] Add an efficient popcount method for integers

STINNER Victor added the comment: New changeset c6b292cdeee689f0bfac6c1e2c2d4e4e01fa8d9e by Victor Stinner in branch 'master': bpo-29882: Add _Py_popcount32() function (GH-20518) https://github.com/python/cpython/commit/c6b292cdeee689f0bfac6c1e2c2d4e4e01fa8d9e -- __

[issue29882] Add an efficient popcount method for integers

Mark Dickinson added the comment: A couple of other data points: - Swift has nonzeroBitCount: https://developer.apple.com/documentation/swift/int/2886050-nonzerobitcount - Rust has count_ones: https://doc.rust-lang.org/std/primitive.u64.html - Go's math/bits package has OnesCount - The clo

[issue29882] Add an efficient popcount method for integers

Mark Dickinson added the comment: > Why are calling a population count method "bit_count()"? Naming things is hard, but I don't think this is an unreasonable name, and it's not without precedent. Java similarly has Integer.bitCount and BigInteger.bitCount. MySQL has BIT_COUNT. -- _

[issue29882] Add an efficient popcount method for integers

Mark Shannon added the comment: Why are calling a population count method "bit_count()"? That seems likely to cause confusion with "bit_length()". I might reasonable expect that 0b1000.bit_count() be 4, not 1. It does have 4 bits. Whereas 0b1000.population_count() is clearly 1. I have no obj

[issue29882] Add an efficient popcount method for integers

Change by STINNER Victor : -- pull_requests: +19762 pull_request: https://github.com/python/cpython/pull/20518 ___ Python tracker ___ __

[issue29882] Add an efficient popcount method for integers

Mark Dickinson added the comment: New changeset 8bd216dfede9cb2d5bedb67f20a30c99844dbfb8 by Niklas Fiekas in branch 'master': bpo-29882: Add an efficient popcount method for integers (#771) https://github.com/python/cpython/commit/8bd216dfede9cb2d5bedb67f20a30c99844dbfb8 -- ___

[issue29882] Add an efficient popcount method for integers

Change by Mark Dickinson : -- resolution: -> fixed stage: -> resolved status: open -> closed versions: +Python 3.10 -Python 3.7 ___ Python tracker ___ ___

[issue29882] Add an efficient popcount method for integers

Mark Dickinson added the comment: PR is updated and mergeable. -- ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscr

[issue29882] Add an efficient popcount method for integers

Mark Dickinson added the comment: > For example, should numpy.int64 get this method as well? That's for the NumPy folks to decide (and I've added Nathaniel Smith to the nosy in case he wants to comment), but I don't see any particularly strong reason that NumPy would need to add it. It looks

[issue29882] Add an efficient popcount method for integers

STINNER Victor added the comment: > In CPython itself: See count_set_bits in Modules/mathmodule.c Python/hamt.c contains an optimized function: static inline uint32_t hamt_bitcount(uint32_t i) { /* We could use native popcount instruction but that would require to either add config

[issue29882] Add an efficient popcount method for integers

STINNER Victor added the comment: Adding a function to a new hypothetical imath module sounds reasonable. I'm less comfortable with adding a new method to int type: it would mean that any int subtype "should" implement it. For example, should numpy.int64 get this method as well? What is the

[issue29882] Add an efficient popcount method for integers

Tim Peters added the comment: I see I never explicitly said +1, so I will now: +1 on merging this :-) -- ___ Python tracker ___ ___

[issue29882] Add an efficient popcount method for integers

Mark Dickinson added the comment: I'm re-reviewing this discussion three years on. I'd be happy for this to go into 3.10. Are there other strong opinions? It would be good to either update and merge the PR, or close as rejected. -- ___ Python trac

[issue29882] Add an efficient popcount method for integers

Tim Peters added the comment: I prefer that a negative int raise ValueError, but am OK with it using the absolute value instead (i.e., what it does now). -- ___ Python tracker __

[issue29882] Add an efficient popcount method for integers

Mark Dickinson added the comment: > I am going to add the imath module. Aimed at 3.8, or 3.9? This seems somewhat rushed for 3.8. -- ___ Python tracker ___ __

[issue29882] Add an efficient popcount method for integers

Mark Dickinson added the comment: > Is everyone comfortable with how negative numbers are handled by this patch? Not entirely, but it's not terribly wrong and it's consistent with how `int.bit_length` works. (I'm also a bit uncomfortable about `int.bit_length`s behaviour on negative numbers,

[issue29882] Add an efficient popcount method for integers

Serhiy Storchaka added the comment: I am going to add the imath module. If we decide to add popcount(), it may be better to add it in this module instead of int class. -- ___ Python tracker

[issue29882] Add an efficient popcount method for integers

Raymond Hettinger added the comment: Is everyone comfortable with how negative numbers are handled by this patch? It might be better to limit the domain and raise a ValueError rather than make a presumption about what the user intends. -- nosy: +rhettinger _

[issue29882] Add an efficient popcount method for integers

Change by Tamás Bajusz : -- nosy: +gbtami ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.

[issue29882] Add an efficient popcount method for integers

Case Van Horsen added the comment: I like the name bit_count and I'll gladly add it to gmpy2 with the appropriate changes to exceptions, etc. -- nosy: +casevh ___ Python tracker ___

[issue29882] Add an efficient popcount method for integers

Tim Peters added the comment: See also: https://en.wikipedia.org/wiki/Hamming_weight As that says, there are a number of languages and processors with first class support for a popcount function. I've frequently implemented it in Python when using integers as integer bitsets (`i` is in t

[issue29882] Add an efficient popcount method for integers

Serhiy Storchaka added the comment: I think that adding bitarray or bitset (or both) in the stdlib would better satisfy the needs. There are open issues for adding ability to read or set selected bits or range of bits in int or for bitwise operations on bytes. I think that bitarray and bitset

[issue29882] Add an efficient popcount method for integers

Mark Dickinson added the comment: Many of those applications are really for bitstrings (chess bitboards, hamming distance), which aren't really the same thing as integers. Nice find for the mathmodule.c case. I'd forgotten about that one (though according to git blame, apparently I'm responsib

[issue29882] Add an efficient popcount method for integers

Niklas Fiekas added the comment: Searching popcount in Python files on GitHub yields a considerable number of examples: https://github.com/search?utf8=%E2%9C%93&q=popcount+extension%3Apy&type=Code Perhaps intresting: * In CPython itself: See count_set_bits in Modules/mathmodule.c * Domain s

[issue29882] Add an efficient popcount method for integers

Mark Dickinson added the comment: Can you give some examples of concrete use-cases? I've spent the last six years or so writing scientific applications and parsing all sorts of odd binary formats, and haven't needed or wanted a popcount yet. > (I am not a fan of the arbitrary return value). A

[issue29882] Add an efficient popcount method for integers

Changes by Jim Fasarakis-Hilliard : -- nosy: +Jim Fasarakis-Hilliard ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscr

[issue29882] Add an efficient popcount method for integers

Changes by Niklas Fiekas : -- pull_requests: +678 ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.

[issue29882] Add an efficient popcount method for integers

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