[bugs.ruby][Feature #20163] 数値を2進数に置き換えたときに 1 の数を返す #bit_count を追加する提案

[Feature #20163] Introduce #bit_count method on Integer

• 数値を2進数に置き換えたときに 1 の数を返す #bit_count を追加する提案

n = 19
p n.bit_count      #=> 3
p (-n).bit_count   #=> 3

# 以下と対等
p n.to_s(2).count("1")   #=> 4

• ビルドインで実装した場合には単純に7倍早くなっているみたいですね
  • https://bugs.ruby-lang.org/issues/20163#note-6

(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

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