[ruby-core:116083] [Ruby master Feature#20163] Introduce #bit_count method on Integer
Issue #20163 has been reported by garrison (Garrison Jensen). ---------------------------------------- Feature #20163: Introduce #bit_count method on Integer https://bugs.ruby-lang.org/issues/20163 * Author: garrison (Garrison Jensen) * Status: Open * Priority: Normal ---------------------------------------- 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/
Issue #20163 has been updated by Eregon (Benoit Daloze). The name sounds too close to `#bit_length`, and `length` and `count` are often quite close in Ruby (e.g. Enumerable#count without arguments is the same as #size/#length after Enumerable#to_a or on an Array, Hash, etc). I think `count_ones` is a better name because there is no ambiguity. [`popcount`](https://en.cppreference.com/w/cpp/numeric/popcount) might be another common name for it, but that seems less clear unless the term or the assembly instruction is already known. Also I think abbreviations are in general suboptimal in method names. ---------------------------------------- Feature #20163: Introduce #bit_count method on Integer https://bugs.ruby-lang.org/issues/20163#change-106080 * Author: garrison (Garrison Jensen) * Status: Open * Priority: Normal ---------------------------------------- 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/
Issue #20163 has been updated by shyouhei (Shyouhei Urabe). count_ones could be something different from what the OP wants, because (-19).bit_count is expected to be 3. PS. `i64::count_ones(-19)` is `62` for Rust. PPS. There is no such thing like a 64bit signed integer in ruby. ---------------------------------------- Feature #20163: Introduce #bit_count method on Integer https://bugs.ruby-lang.org/issues/20163#change-106099 * Author: garrison (Garrison Jensen) * Status: Open * Priority: Normal ---------------------------------------- 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/
Issue #20163 has been updated by nobu (Nobuyoshi Nakada). GCC has `__builtin_popcount` and Ruby defines `rb_popcount` function family internally. ---------------------------------------- Feature #20163: Introduce #bit_count method on Integer https://bugs.ruby-lang.org/issues/20163#change-106103 * Author: garrison (Garrison Jensen) * Status: Open * Priority: Normal ---------------------------------------- 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/
Issue #20163 has been updated by byroot (Jean Boussier). I also think `popcount` makes sense. Yes it's a bit of a cryptic name, but if you are dealing with bits, you are likely to be familiar with that name. ---------------------------------------- Feature #20163: Introduce #bit_count method on Integer https://bugs.ruby-lang.org/issues/20163#change-106107 * Author: garrison (Garrison Jensen) * Status: Open * Priority: Normal ---------------------------------------- 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/
Issue #20163 has been updated by garrison (Garrison Jensen). I like `popcount`, and have no strong preferences for the chosen name. I want to share my performance tests in case they are helpful for the discussion. As you can see, the built-in method is significantly faster. ``` (0..10_000_000).each { |x| x.to_s(2).count('1') } processing time: 3.714706s (0..10_000_000).each { |x| ruby_pop_count(x) } processing time: 3.367775s (0..10_000_000).each { |x| x.pop_count } processing time: 0.515767s ``` Here are my implementations: ``` def ruby_pop_count(n) n = n.abs count = 0 while n > 0 n &= n - 1 count += 1 end count end ``` ``` unsigned int pop_count(long value) { #ifdef __GNUC__ // Use GCC built-in return __builtin_popcountl(value); #else // Fallback method for compilers without the built-in unsigned int count = 0; while (value) { count += value & 1; value >>= 1; } return count; #endif } // Wrapper function for Ruby VALUE rb_pop_count(VALUE self) { long value = NUM2LONG(self); unsigned int count = pop_count(labs(value)); return UINT2NUM(count); } ``` ---------------------------------------- Feature #20163: Introduce #bit_count method on Integer https://bugs.ruby-lang.org/issues/20163#change-106136 * Author: garrison (Garrison Jensen) * Status: Open * Priority: Normal ---------------------------------------- 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/
Issue #20163 has been updated by tenderlovemaking (Aaron Patterson). I would also like a `popcount` method. I prefer `popcount` over `bit_count`. I wrote my own [here](https://github.com/tenderlove/bitz/blob/93cedfe8f571e106ced753b3060c92507845...) (but it only deals with single bytes). ---------------------------------------- Feature #20163: Introduce #bit_count method on Integer https://bugs.ruby-lang.org/issues/20163#change-114429 * 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/
Issue #20163 has been updated by akr (Akira Tanaka). What is the behavior for negative values? The proposal describes two implenentations that returns different values. ``` p (-5).to_s(2).count("1") #=> 2 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 p bit_count(-5) #=> 0 ``` ---------------------------------------- Feature #20163: Introduce #bit_count method on Integer https://bugs.ruby-lang.org/issues/20163#change-114430 * 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/
Issue #20163 has been updated by byroot (Jean Boussier).
What is the behavior for negative values?
IMO, the only behavior that makes sense in the context of a language with arbitrary size integers is to ignore the sign bit. ---------------------------------------- Feature #20163: Introduce #bit_count method on Integer https://bugs.ruby-lang.org/issues/20163#change-114434 * 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/
Issue #20163 has been updated by mame (Yusuke Endoh). What are the intended use cases for this proposal? My experience (in other languages) involves two use cases of popcount: * Bitboards for game AI (like Reversi) to count pieces. * Succinct data structures (like LOUDS Tries) for rank operations. In both scenarios, integers are treated as unsigned bitsets. Does anyone have a use case where popcount on a negative number is necessary? If not, I guess raising an exception would be the best behavior. ---------------------------------------- Feature #20163: Introduce #bit_count method on Integer https://bugs.ruby-lang.org/issues/20163#change-114446 * 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/
Issue #20163 has been updated by tompng (tomoya ishida). I also think popcount of a negative number should raise error because of the ambiguity. One way to extend popcount to negative number is using a relationship below, derived from the fact that `-5 == 0b111...11111011` has 1 fewer bits compared to `-1 == 0b111...11111111`. ~~~ruby x.popcount == popcount_of_minus_one - (~x).popcount # popcount_of_minus_one: 0 or -1 or something else representing infinity bits ~~~ I'm not sure if this definition is useful, but anyway, extending to negative number has ambiguity. If someone want a popcount of abs, `n.abs.popcount` is clearer. ---------------------------------------- Feature #20163: Introduce #bit_count method on Integer https://bugs.ruby-lang.org/issues/20163#change-114447 * 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/
Issue #20163 has been updated by ahorek (Pavel Rosický). x64 and ARM have specialized CPU instructions https://godbolt.org/z/xvGvzsvd9 and Ruby already uses it internally, for instance https://github.com/ruby/ruby/blob/dc555a48e750b4d50eb7a7000ca1bfb927fa9459/s... That said, Ruby isn’t the ideal choice for implementing memory allocators, SIMD masks, parity checks, GCD calculations, UTF parsers, or prime sieving… but since many other languages, even Python, provide support for popcount, why not? ---------------------------------------- Feature #20163: Introduce #bit_count method on Integer https://bugs.ruby-lang.org/issues/20163#change-114448 * 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/
Issue #20163 has been updated by byroot (Jean Boussier).
but since many other languages, even Python, provide support for popcount, why not?
Usually a higher bar than that is required for a new method to be added to Ruby. I personally don't have an immediate use case to point to (except for Aaron's gem of course). But more generally, in recent years we've tried to eliminate or at least reduce the need for C extensions, and bit operation are often useful in these cases, so I'm sympathetic to more bit oriented capacities. ---------------------------------------- Feature #20163: Introduce #bit_count method on Integer https://bugs.ruby-lang.org/issues/20163#change-114449 * 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/
Issue #20163 has been updated by tenderlovemaking (Aaron Patterson). mame (Yusuke Endoh) wrote in #note-10:
What are the intended use cases for this proposal?
My experience (in other languages) involves two use cases of popcount:
* Bitboards for game AI (like Reversi) to count pieces. * Succinct data structures (like LOUDS Tries) for rank operations.
In both scenarios, integers are treated as unsigned bitsets.
My experience is similar. I've used it for sets (like I linked above) as well as modeling [undirected graphs](https://tenderlovemaking.com/2023/03/19/bitmap-matrix-and-undirected-graphs-...) (a bit matrix, but I omitted popcount from the blog post). I've only used unsigned integers, and I think it would be a bug in my code if the integers were signed.
Does anyone have a use case where popcount on a negative number is necessary? If not, I guess raising an exception would be the best behavior.
I agree, and I think it should raise an exception. ahorek (Pavel Rosický) wrote in #note-12:
That said, Ruby isn’t the ideal choice for implementing memory allocators, SIMD masks, parity checks, GCD calculations, UTF parsers, or prime sieving…
Not yet! But hopefully someday! 😂 ---------------------------------------- Feature #20163: Introduce #bit_count method on Integer https://bugs.ruby-lang.org/issues/20163#change-114450 * 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/
Issue #20163 has been updated by garrison (Garrison Jensen). [Python ignores the sign](https://docs.python.org/3/library/stdtypes.html#int.bit_count). It seems friendlier to match that behavior than throw an exception. ``` ruby (-x).popcount == x.popcount ``` ---------------------------------------- Feature #20163: Introduce #bit_count method on Integer https://bugs.ruby-lang.org/issues/20163#change-114451 * 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/
Issue #20163 has been updated by tenderlovemaking (Aaron Patterson). garrison (Garrison Jensen) wrote in #note-15:
[Python ignores the sign](https://docs.python.org/3/library/stdtypes.html#int.bit_count). It seems friendlier to match that behavior than throw an exception.
``` ruby (-x).popcount == x.popcount ```
When would you use a negative number unless it's a mistake in your code? ---------------------------------------- Feature #20163: Introduce #bit_count method on Integer https://bugs.ruby-lang.org/issues/20163#change-114453 * 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/
Issue #20163 has been updated by tenderlovemaking (Aaron Patterson). It seems like the Python folks didn't have too serious a discussion about handling negative numbers. https://github.com/python/cpython/issues/74068#issuecomment-1093743975 https://github.com/python/cpython/issues/74068#issuecomment-1093743978 I prefer it raises an exception as it's probably a mistake in the code. 🤷🏻♀️ ---------------------------------------- Feature #20163: Introduce #bit_count method on Integer https://bugs.ruby-lang.org/issues/20163#change-114454 * 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/
Issue #20163 has been updated by garrison (Garrison Jensen). tenderlovemaking (Aaron Patterson) wrote in #note-16:
When would you use a negative number unless it's a mistake in your code?
I don't have a strong argument. Raising an exception sounds good to me. ---------------------------------------- Feature #20163: Introduce #bit_count method on Integer https://bugs.ruby-lang.org/issues/20163#change-114455 * 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/
Issue #20163 has been updated by akr (Akira Tanaka). I prefer an exception for popcount to negative values. I think an array of Fixnums (63 bit signed integers) can be used for mutable bit array. (Ruby's Integer is immutable. So mutable bit array needs a mutable data structure.) In this scenario, we would like to count bits in a negative fixnum: `(n & 0x7ffffffff).popcount`. This is not `n.abs.popcount`. Also, this behavior is not suitable for Integer#popcount because it ignores bits higher than 63th bit. So, I prefer an exception for negative values. ---------------------------------------- Feature #20163: Introduce #bit_count method on Integer https://bugs.ruby-lang.org/issues/20163#change-114487 * 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/
Issue #20163 has been updated by slewsys (Andrew Moore). garrison (Garrison Jensen) wrote in #note-6:
``` unsigned int pop_count(long value) { #ifdef __GNUC__ // Use GCC built-in return __builtin_popcountl(value); #else // Fallback method for compilers without the built-in unsigned int count = 0; while (value) { count += value & 1; value >>= 1; } return count; #endif }
// Wrapper function for Ruby VALUE rb_pop_count(VALUE self) { long value = NUM2LONG(self); unsigned int count = pop_count(labs(value)); return UINT2NUM(count); } ```
Section 1.8 of *Matters Computational* by Jörg Arndt offers efficient algorithms for popcount, including for arrays. There is also an x86 instruction POPCNT. Matters Computational: https://www.jjj.de/fxt/fxtbook.pdf E.g., ``` unsigned long popcount (unsigned long value) { value -= (value >> 1) & 0x5555555555555555UL; value = ((value >> 2) & 0x3333333333333333UL) + (value & 0x3333333333333333UL); value = ((value >> 4) + value) & 0x0f0f0f0f0f0f0f0fUL; value *= 0x0101010101010101UL; return value >> 56; } ``` By the way, "popcount" is short for "population count", whereas "pop_count" suggests (to me) a stack operation - a bit (hm) confusing. ---------------------------------------- Feature #20163: Introduce #bit_count method on Integer https://bugs.ruby-lang.org/issues/20163#change-114663 * 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/
Issue #20163 has been updated by YO4 (Yoshinao Muramatsu). We can use Integer#[] to negative numbers. ``` -1[0,8].popcount # => 8 -2[0,8].popcount # => 7 -3[0,8].popcount # => 7 ``` In computers that use two's complement for negative numbers, I think this is expected behavior. If generating sliced values becomes an overhead, we can add arguments to popcount. ---------------------------------------- Feature #20163: Introduce #bit_count method on Integer https://bugs.ruby-lang.org/issues/20163#change-114697 * 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/
Issue #20163 has been updated by mame (Yusuke Endoh).
In computers that use two's complement for negative numbers, I think this is expected behavior.
Yes, but do you want `-1.popcount` to return `Float::INFINITY`? That might be theoretically consistent, but useless and even problematic, I think. ---------------------------------------- Feature #20163: Introduce #bit_count method on Integer https://bugs.ruby-lang.org/issues/20163#change-114702 * 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/
Issue #20163 has been updated by YO4 (Yoshinao Muramatsu). Popcount for negative numbers is useful when equivalent functionality to machine register operations is desired, but I do not consider operations on infinite bit widths to be useful. When popcount is called on a negative number (without specifying a bit width if popcount has arguments), it may indicate abnormal input or a bug in user code. I am +1 for raising exception on that case. ---------------------------------------- Feature #20163: Introduce #bit_count method on Integer https://bugs.ruby-lang.org/issues/20163#change-114709 * 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/
Issue #20163 has been updated by matz (Yukihiro Matsumoto). Is there any real-world use-case for Integer#popcount method? Bit-array? Matz. ---------------------------------------- Feature #20163: Introduce #bit_count method on Integer https://bugs.ruby-lang.org/issues/20163#change-114907 * 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/
Issue #20163 has been updated by tenderlovemaking (Aaron Patterson). matz (Yukihiro Matsumoto) wrote in #note-24:
Is there any real-world use-case for Integer#popcount method? Bit-array?
Matz.
Yes, I am using it for a [bit set gem](https://github.com/tenderlove/bitz) (I had to implement my own popcount [here](https://github.com/tenderlove/bitz/blob/3570f8dfd3aec46bc9ffac03ef5e85fb26cc...)). I want to use a bit array for representing an undirected graph. ---------------------------------------- Feature #20163: Introduce #bit_count method on Integer https://bugs.ruby-lang.org/issues/20163#change-114917 * 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/
Issue #20163 has been updated by jhawthorn (John Hawthorn). I have a real-world use case: I've been working on a pure-Ruby [Hash Array Mapped Trie (HAMT)](https://en.wikipedia.org/wiki/Hash_array_mapped_trie) https://github.com/jhawthorn/hamt. I want this because having an immutable hash-table-like map which can be cheaply copied/modified would be helpful for sharing data between Ractors. The implementation of HAMT requires popcount: for each node in the tree we have a 32-bit bitmap representing which keys are present, and an array containing the keys/values. At each level we test for a key's presence using 5 bits of it's hash value `bit = 1 << ((hash >> level) & 31)`. If that bit is set, we find where it exists in the array using `popcount(bitmap & (bit - 1))` (feels similar to succinct bit vector). The `String#bit_count` proposed in another issues (#22082/#22118) would not be a good fit here. I don't want an additional String object per-node. I'm always representing at most 32 bits (this is the typical choice for HAMT) in a fixnum. I'd also need either a way to mask only the relevant bits from the string, requiring an extra allocation (I actually don't even see a way to do this with what is in #22118). We also have the endianness issue. This is all avoided and natural with Integer. There are other textbook uses for popcount out there: hamming distance, parity, etc. I think `Integer#bit_count` makes sense and is aligned with existing use of Integer. We have `bit_length` which is a very similar concept and name and have many other functions for dealing with bits on integer (`Integer#[]`, `#allbits?`, `#anybits?`, bitwise operations, etc) ---------------------------------------- Feature #20163: Introduce #bit_count method on Integer https://bugs.ruby-lang.org/issues/20163#change-117908 * 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/
Issue #20163 has been updated by jhawthorn (John Hawthorn). I tried finding uses in the wild via gem-codesearch. I only looked for `to_s(2).count("1")` which is a pretty inefficient way to `bit_count`, so this would miss any gems which used another technique (a loop or some bit twiddling) to count bits. Still it found a few use cases: **CIDR/netmask** Very common to do some variation of `IPAddr.new(mask).to_i.to_s(2).count("1")` to get the prefix length of the netmask. Done by: sequel, facter, inspec-core, vagrant, and many others 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). **Hamming distance** For example [dhash-vips.rb](https://github.com/nakilon/dhash-vips/blob/master/lib/dhash-vips.rb) doing `to_s(2).count("1")` to get hamming distance for perceptual similarity Also: simhash2, chromaprint, edits, dhash, dhasher, and others Also found in [unicode_plot](https://github.com/red-data-tools/unicode_plot.rb/blob/4c313e47449d894d055cc...) using a different pattern: `(i ^ k).digits(2).sum` **Parity bit** For example in https://github.com/larskanis/pkcs11 `n.to_s(2).count("1").odd?` **sigstore-ruby** I only found sigstore Ruby doing this, something involving proof verification in a Merkle tree (?). It requires both bit_length (which already exists) and bit_count (being proposed here). `(log_index >> inner).to_s(2).count("1")` https://github.com/sigstore/sigstore-ruby/blob/26ffbe0c1d6e16614fb9cd8b2ed40... Note: I believe this was ported from go which has a popcount (`bits.OnesCount64`) method. ---------------------------------------- Feature #20163: Introduce #bit_count method on Integer https://bugs.ruby-lang.org/issues/20163#change-117911 * 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/
Issue #20163 has been updated by jhawthorn (John Hawthorn). I've opened a PR implementing `Integer#bit_count` https://github.com/ruby/ruby/pull/17696 For negative numbers this raises `Math::DomainError`, same as `Integer#digits` when called with a negative number ---------------------------------------- Feature #20163: Introduce #bit_count method on Integer https://bugs.ruby-lang.org/issues/20163#change-117928 * 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/
Issue #20163 has been updated by tenderlovemaking (Aaron Patterson). I found a few more examples "in the wild": * [MOBI parser/generator](https://github.com/slonopotamus/dyck/blob/b031a8b396e55067d78c6ff85ff4f0f3bb...) * [TON blockchain SDK](https://github.com/nerzh/ton-sdk-ruby/blob/42d482c180426b6b565c3e1fe31bfe2d2...) * [ARM64 encoder](https://github.com/tenderlove/aarch64/blob/27d2ed1088f8babda48006dc8bf4e057c...) * [Another IP address library](https://github.com/izawa/cidr/blob/73e7af76138b46f32e37a8e7b57ad966493ecd49/...) ---------------------------------------- Feature #20163: Introduce #bit_count method on Integer https://bugs.ruby-lang.org/issues/20163#change-117929 * 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/
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/
Issue #20163 has been updated by jhawthorn (John Hawthorn). mame (Yusuke Endoh) wrote in #note-31:
but [CIDR] clearly seems like a case where `n.bit_length`, not popcount, is the correct choice.
I do think popcount is the right choice for CIDR. That's what everything other than `IPAddr` is using and it directly returns the correct result (all implementations we've looked at assume the netmask has a valid CIDR notation). The code in `IPAddr` is doing bit_length in a loop currently, but if you look at [the full code](https://github.com/ruby/ruby/blob/master/lib/ipaddr.rb#L464-L480). It actually needs to xor with `IN4MASK`/`IN6MASK` and then subtract the bit_length from 32 or 128. Using bit_length we'd still need to xor and subtract: ```ruby def prefix case @family when Socket::AF_INET 32 - (IN4MASK ^ @mask_addr).bit_length when Socket::AF_INET6 128 - (IN6MASK ^ @mask_addr).bit_length # may allocate in xor? else raise AddressFamilyError, "unsupported address family" end end ``` `bit_count` is a lot more natural (the only complexity is in validating the address family) ```ruby case @family when Socket::AF_INET, Socket::AF_INET6 @mask_addr.bit_count else raise AddressFamilyError, "unsupported address family" end ```
`leading_ones`
This method seems very confusing to me. It's common to have a ["count leading zeros" (clz)](https://en.wikipedia.org/wiki/Find_first_set), but that only makes sense with fixed precision (in cases in Ruby we'd want "count leading zeros" we'd likely use `bit_length`). "leading ones" sounds like it would be the same thing. Does this have any outside out of CIDR (where it is always equal to popcount)? I think we can perform this using `bit_length` (it is a bit awkward and would allocate when `n` is a bignum): ```ruby def leading_ones(n) n.bit_length - (n ^ ((1 << n.bit_length) - 1)).bit_length end ```
`trailing_zeros`
I think this makes a lot more sense and is a common operation in other languages. I'd support it's inclusion, but I think it's less important than popcount. I think we can perform this using bit_length (though it allocates when `n` is a bignum) ```ruby def trailing_zeros(n) return 0 if n.zero? (n ^ (n - 1)).bit_length - 1 end ``` ---------------------------------------- Feature #20163: Introduce #bit_count method on Integer https://bugs.ruby-lang.org/issues/20163#change-117952 * 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/
Issue #20163 has been updated by jhawthorn (John Hawthorn). Couple notes on the various gems mame (Yusuke Endoh) wrote in #note-31:
* **Parity bit**: I couldn't find the relevant code in larskanis/pkcs11.
Sorry, the quoted code was from another library. Here it is: https://github.com/larskanis/pkcs11/blob/12d868912e0d17aa41e497f9bb99f66a397... Another example of parity: https://gitlab.com/pkerling/subconv/-/blob/e560905808b2db0918b0e350f39b13690...
* **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`.
These aren't equivalent. This is checking that MORE than one bit is set, I don't know why but [other mobi libraries in other languages](https://github.com/bfabiszewski/libmobi/blob/906274205c11944b628da1c553b255a...) seem to as well. But I agree there's another way to test for this: `x & (x - 1) != 0`
* **nerzh/ton-sdk-ruby**: This one is genuinely popcount. Worth noting that this library also defines `clz`.
It defines `clz` (for 32 bits by default), but only seems to use it in `level` as `32 - clz(value)`, which is actually `bit_length`. So this is another case `bit_count` is complementing `bit_length`. ---------------------------------------- Feature #20163: Introduce #bit_count method on Integer https://bugs.ruby-lang.org/issues/20163#change-117953 * 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/
Issue #20163 has been updated by matz (Yukihiro Matsumoto). Accepted, with one change from the proposal: `bit_count` on a negative integer shall raise `ArgumentError` instead of using the absolute value. A negative integer in Ruby is conceptually an infinite two's complement bit string, so its population count is not well defined, and silently using the absolute value could mask bugs. The name `bit_count` is good. In Ruby, `count` means counting matching or present things (`Array#count`, `String#count`), as opposed to `length`, which is the trivial total extent. Viewing an integer as a bit set, the set bits are exactly the elements present, so `bit_count` naturally reads as the number of set bits, and it is clearly distinguished from `bit_length`. It also fits the `bit_at` / `bitwise_*` vocabulary being discussed for `String` in #22082/#22118; if we later add the same operation to `String`, it shall use the same name. Matz. ---------------------------------------- Feature #20163: Introduce #bit_count method on Integer https://bugs.ruby-lang.org/issues/20163#change-118022 * 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/
participants (14)
-
ahorek -
akr (Akira Tanaka)
-
byroot (Jean Boussier)
-
Eregon (Benoit Daloze)
-
garrison (Garrison Jensen)
-
jhawthorn (John Hawthorn)
-
mame (Yusuke Endoh)
-
matz (Yukihiro Matsumoto)
-
nobu (Nobuyoshi Nakada)
-
shyouhei (Shyouhei Urabe)
-
slewsys (Andrew Moore)
-
tenderlovemaking (Aaron Patterson)
-
tompng (tomoya ishida)
-
YO4 (Yoshinao Muramatsu)