Feature #20163
openIntroduce #bit_count method on Integer
Description
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
Updated by Eregon (Benoit Daloze) 10 months ago
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
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.
Updated by shyouhei (Shyouhei Urabe) 10 months ago
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.
Updated by nobu (Nobuyoshi Nakada) 10 months ago
GCC has __builtin_popcount
and Ruby defines rb_popcount
function family internally.
Updated by byroot (Jean Boussier) 10 months ago
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.
Updated by nobu (Nobuyoshi Nakada) 10 months ago
- Is duplicate of Feature #8748: Integer#popcount (Fixnum#popcount and Bignum#popcount) added
Updated by garrison (Garrison Jensen) 10 months ago
I like popcount
but I also like count_ones
because it sounds friendlier, however I have no strong preferences for the chosen name.
Also, 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);
}