4 ms·

What is the use case for int.bit_count [1] which returns the number of ones in the binary representation of the integer? [1]: https://docs.python.org/3/library

What is the use case for int.bit_count [1] which returns the number of ones in the binary representation of the integer? [1]: https://docs.python.org/3/library/stdtypes.html#int.bit_count https://docs.python.org/3/library/stdtypes.html#int.bit_coun...

sio8ohPi 4y ago
https://en.wikipedia.org/wiki/Hamming_weight https://en.wikipedia.org/wiki/Hamming_weight I guess it's included as an easy way to access the fast hardware supported implementation, on architectures where it is available.
- saagarjha 4y ago
  Sadly it does not call into the hardware implementation: https://github.com/python/cpython/blob/f62ad4f2c4214fdc05cc45c27a5c068553c7942c/Objects/longobject.c#L5711 https://github.com/python/cpython/blob/f62ad4f2c4214fdc05cc4...
  - orlp 4y ago
    It does. Note that it calls popcount_digit on each digit of the integer (a 'digit' here is 32 bits), which calls _Py_popcount32, which does map to a hardware instruction if possible: https://github.com/python/cpython/blob/f62ad4f2c4214fdc05cc45c27a5c068553c7942c/Include/internal/pycore_bitutils.h#L95 https://github.com/python/cpython/blob/f62ad4f2c4214fdc05cc4...
    - saagarjha 4y ago
      Ah, you are correct. Although I still take issue with "fast" in the comment I was replying to ;)
newbye3 4y ago
If you are using integers to represent subsets then int.bit_count is the number of elements of the set. There is a machine instruction to count the number of ones in the binary representation, maybe popcnt is the name, I am not sure. Edited, more info: AMD's Barcelona architecture introduced the advanced bit manipulation (ABM) ISA introducing the POPCNT instruction as part of the SSE4a extensions in 2007. Intel Core processors introduced a POPCNT instruction with the SSE4.2 instruction set extension, first available in a Nehalem-based Core i7 processor, released in November 2008. https://www.rosettacode.org/wiki/Population_count https://www.rosettacode.org/wiki/Population_count
clappski 4y ago
Sometimes you might use bits in an integer to encode data, e.g.; - A bitset index - Bitflags (e.g. to represent logging levels) - Feature flags `bit_count` (aka `popcount`) gives you an efficient way to figure out how many bits within those structures are set and not set.
josefx 4y ago
Never used in python, but I had some C++ code where I used bit sets to identify which values in an array where valid, in that context the amount of ones was the amount of valid entries.
joshvm 4y ago
A common use is the Hamming distance, which is the number of different bits between two streams. It comes up in things like the census transform, which is used for image matching. https://www.researchgate.net/figure/Census-transform-and-Hamming-distance-for-3-x-3-windows_fig2_261269856 https://www.researchgate.net/figure/Census-transform-and-Ham...
mattkrause 4y ago
It’s surprisingly useful, and shows up everywhere from chess to molecular biology—-but the CPU instruction probably exists because of its use in code-breaking. This article has a lot of interesting examples. https://vaibhavsagar.com/blog/2019/09/08/popcount/ https://vaibhavsagar.com/blog/2019/09/08/popcount/

sio8ohPi 4y ago

https://en.wikipedia.org/wiki/Hamming_weight https://en.wikipedia.org/wiki/Hamming_weight I guess it's included as an easy way to access the fast hardware supported implementation, on architectures where it is available.

saagarjha 4y ago
Sadly it does not call into the hardware implementation: https://github.com/python/cpython/blob/f62ad4f2c4214fdc05cc45c27a5c068553c7942c/Objects/longobject.c#L5711 https://github.com/python/cpython/blob/f62ad4f2c4214fdc05cc4...
- orlp 4y ago
  It does. Note that it calls popcount_digit on each digit of the integer (a 'digit' here is 32 bits), which calls _Py_popcount32, which does map to a hardware instruction if possible: https://github.com/python/cpython/blob/f62ad4f2c4214fdc05cc45c27a5c068553c7942c/Include/internal/pycore_bitutils.h#L95 https://github.com/python/cpython/blob/f62ad4f2c4214fdc05cc4...
  - saagarjha 4y ago
    Ah, you are correct. Although I still take issue with "fast" in the comment I was replying to ;)

newbye3 4y ago

If you are using integers to represent subsets then int.bit_count is the number of elements of the set. There is a machine instruction to count the number of ones in the binary representation, maybe popcnt is the name, I am not sure. Edited, more info: AMD's Barcelona architecture introduced the advanced bit manipulation (ABM) ISA introducing the POPCNT instruction as part of the SSE4a extensions in 2007. Intel Core processors introduced a POPCNT instruction with the SSE4.2 instruction set extension, first available in a Nehalem-based Core i7 processor, released in November 2008. https://www.rosettacode.org/wiki/Population_count https://www.rosettacode.org/wiki/Population_count

clappski 4y ago

Sometimes you might use bits in an integer to encode data, e.g.; - A bitset index - Bitflags (e.g. to represent logging levels) - Feature flags `bit_count` (aka `popcount`) gives you an efficient way to figure out how many bits within those structures are set and not set.

josefx 4y ago

Never used in python, but I had some C++ code where I used bit sets to identify which values in an array where valid, in that context the amount of ones was the amount of valid entries.

joshvm 4y ago

A common use is the Hamming distance, which is the number of different bits between two streams. It comes up in things like the census transform, which is used for image matching. https://www.researchgate.net/figure/Census-transform-and-Hamming-distance-for-3-x-3-windows_fig2_261269856 https://www.researchgate.net/figure/Census-transform-and-Ham...

mattkrause 4y ago

It’s surprisingly useful, and shows up everywhere from chess to molecular biology—-but the CPU instruction probably exists because of its use in code-breaking. This article has a lot of interesting examples. https://vaibhavsagar.com/blog/2019/09/08/popcount/ https://vaibhavsagar.com/blog/2019/09/08/popcount/