Feature #20163: Introduce #bit_count method on Integer

• Status: Open
• Assignee: -
• Target version: -

[garrison (Garrison Jensen)]

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

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

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

[nobu (Nobuyoshi Nakada)]

GCC has __builtin_popcount and Ruby defines rb_popcount function family internally.

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

[nobu (Nobuyoshi Nakada)]

• Is duplicate of Feature #8748: Integer#popcount (Fixnum#popcount and Bignum#popcount) added

[garrison (Garrison Jensen)]

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);
}