Hacker News Reader

Comment by divbzero | Hacker News Reader

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_coun...

View on HN

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

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-Ham...

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.

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.

Sadly it does not call into the hardware implementation: https://github.com/python/cpython/blob/f62ad4f2c4214fdc05cc4...

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/f62ad4f2c4214fdc05cc4...

Ah, you are correct. Although I still take issue with "fast" in the comment I was replying to ;)

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.

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/

Reply on news.ycombinator.com