Project

General

Profile

Actions

Feature #20163

open

Introduce #bit_count method on Integer

Added by garrison (Garrison Jensen) 10 months ago. Updated 10 months ago.

Status:
Open
Assignee:
-
Target version:
-
[ruby-core:116083]

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


Related issues 1 (0 open1 closed)

Is duplicate of Ruby master - Feature #8748: Integer#popcount (Fixnum#popcount and Bignum#popcount)RejectedActions

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.

Actions #5

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

Also available in: Atom PDF

Like1
Like1Like0Like0Like1Like0Like0