[ruby-core:123292] [Ruby Feature#20163] Introduce #bit_count method on Integer

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 =3D 0;
>     while (value) {
>         count +=3D value & 1;
>         value >>=3D 1;
>     }
>     return count;
> #endif
> }
>=20
> // Wrapper function for Ruby
> VALUE rb_pop_count(VALUE self) {
>     long value =3D NUM2LONG(self);
>     unsigned int count =3D  pop_count(labs(value));
>     return UINT2NUM(count);
> }
> ```

Section 1.8 of *Matters Computational* by J=F6rg Arndt offers efficient alg=
orithms for popcount, including for arrays.  There is also an x86 instructi=
on POPCNT.

Matters Computational: https://www.jjj.de/fxt/fxtbook.pdf

E.g.,
```
unsigned long popcount (unsigned long value) {
    value -=3D (value >> 1) & 0x5555555555555555UL;
    value =3D ((value >> 2) & 0x3333333333333333UL) + (value & 0x3333333333=
333333UL);
    value =3D ((value >> 4) + value) & 0x0f0f0f0f0f0f0f0fUL;
    value *=3D 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 absolut=
e value of the integer.
```
n =3D 19
n.bit_count #=3D> 3
(-n).bit_count #=3D> 3
```
This is often useful when you use an integer as a bitmask and want to count=
 how many bits are set.=20

This would be equivalent to
```
n.to_s(2).count("1")
```

However, this can be outperformed by
```
def bit_count(n)
  count =3D 0
  while n > 0
    n &=3D n - 1 # Flip the least significant 1 bit to 0
    count +=3D 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 t=
o performance often results in a significant improvement.=20

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



--=20
https://bugs.ruby-lang.org/
______________________________________________
 ruby-core mailing list -- [e-mail]
 To unsubscribe send an email to [e-mail]
 ruby-core info -- https://ml.ruby-lang.org/mailman3/lists/ruby-core.ml.rub=
y-lang.org/