Issue #20163 has been updated by mame (Yusuke Endoh). Thanks for the examples. Unless I'm misreading, the popcount usage in Hash Array Mapped Trie is the rank operation from succinct data structures that I mentioned (the operation that finds which bit is the nth set bit). I took a quick look through the other examples you listed. The good news is that (unless I'm misreading) none of the examples appear to deal with negative numbers. Treating negatives as raising an exception is probably fine. On the other hand, whether popcount is really what's needed seems questionable in a few cases: - **CIDR/netmask**: IMO, using popcount here feels a bit tricky. Wouldn't `leading_ones` / `trailing_zeros` be more appropriate? - **Hamming distance**: This one is genuinely popcount. - **Parity bit**: I couldn't find the relevant code in larskanis/pkcs11. - **sigstore-ruby**: This one is genuinely popcount. - **tenderlove/aarch64**: This uses popcount to build an exception message, `raise "Expected a #{popcount(mask)} bit number..."`, so `bit_length` looks like the better choice here. - **izawa/cidr**: This is a netmask case, so `leading_ones` / `trailing_zeros` feels more appropriate. - **slonopotamus/dyck**: This uses it in the form `Dyck.popcount(tagx.bitmask) > 1`, but unless I'm misreading, `tagx.bitmask` seems to be a value like `0b1`, `0b11`, `0b111`, ..., so `bit_length > 1` seems more natural than `popcount > 1`. - **nerzh/ton-sdk-ruby**: This one is genuinely popcount. Worth noting that this library also defines `clz`.
Another case (in stdlib!) is `IPAddr#prefix` which uses a shift loop. If `bit_count` is accepted we should change [the loop in `IPAddr#prefix` to use it](https://github.com/ruby/ipaddr/blob/master/lib/ipaddr.rb#L464-L480).
This code is: ```ruby while n.positive? n >>= 1 i -= 1 end ``` but this clearly seems like a case where `n.bit_length`, not popcount, is the correct choice. To summarize, the cases where I felt popcount is genuinely needed are these four: - rank operation (Succinct data structures / Hash Array Mapped Trie) - Hamming distance - sigstore-ruby - TON SDK By the way, looking at these use cases made me think `leading_ones` and `trailing_zeros` might be desirable too. And the name `bit_count` doesn't extend naturally to those. Also, is `bit_count` a natural name for counting the set bits? TON SDK calls it `count_set_bits`, which felt clearer to me. ---------------------------------------- Feature #20163: Introduce #bit_count method on Integer https://bugs.ruby-lang.org/issues/20163#change-117947 * Author: garrison (Garrison Jensen) * Status: Open ---------------------------------------- This feature request is to implement a method called #bit_count on Integer that returns the number of ones in the binary representation of the absolute value of the integer. ``` n = 19 n.bit_count #=> 3 (-n).bit_count #=> 3 ``` This is often useful when you use an integer as a bitmask and want to count how many bits are set. This would be equivalent to ``` n.to_s(2).count("1") ``` However, this can be outperformed by ``` def bit_count(n) count = 0 while n > 0 n &= n - 1 # Flip the least significant 1 bit to 0 count += 1 end count end ``` I think this would be a useful addition because it would fit alongside the other bit-related methods defined on integer: `#bit_length,` `#allbits?`, `#anybits?`, `#nobits?`. Also, when working with bitmasks, a minor upgrade to performance often results in a significant improvement. Similar methods from other languages: https://docs.python.org/3/library/stdtypes.html#int.bit_count https://doc.rust-lang.org/std/primitive.i32.html#method.count_ones -- https://bugs.ruby-lang.org/