Issue #20163 has been updated by jhawthorn (John Hawthorn). mame (Yusuke Endoh) wrote in #note-31:
but [CIDR] clearly seems like a case where `n.bit_length`, not popcount, is the correct choice.
I do think popcount is the right choice for CIDR. That's what everything other than `IPAddr` is using and it directly returns the correct result (all implementations we've looked at assume the netmask has a valid CIDR notation). The code in `IPAddr` is doing bit_length in a loop currently, but if you look at [the full code](https://github.com/ruby/ruby/blob/master/lib/ipaddr.rb#L464-L480). It actually needs to xor with `IN4MASK`/`IN6MASK` and then subtract the bit_length from 32 or 128. Using bit_length we'd still need to xor and subtract: ```ruby def prefix case @family when Socket::AF_INET 32 - (IN4MASK ^ @mask_addr).bit_length when Socket::AF_INET6 128 - (IN6MASK ^ @mask_addr).bit_length # may allocate in xor? else raise AddressFamilyError, "unsupported address family" end end ``` `bit_count` is a lot more natural (the only complexity is in validating the address family) ```ruby case @family when Socket::AF_INET, Socket::AF_INET6 @mask_addr.bit_count else raise AddressFamilyError, "unsupported address family" end ```
`leading_ones`
This method seems very confusing to me. It's common to have a ["count leading zeros" (clz)](https://en.wikipedia.org/wiki/Find_first_set), but that only makes sense with fixed precision (in cases in Ruby we'd want "count leading zeros" we'd likely use `bit_length`). "leading ones" sounds like it would be the same thing. Does this have any outside out of CIDR (where it is always equal to popcount)? I think we can perform this using `bit_length` (it is a bit awkward and would allocate when `n` is a bignum): ```ruby def leading_ones(n) n.bit_length - (n ^ ((1 << n.bit_length) - 1)).bit_length end ```
`trailing_zeros`
I think this makes a lot more sense and is a common operation in other languages. I'd support it's inclusion, but I think it's less important than popcount. I think we can perform this using bit_length (though it allocates when `n` is a bignum) ```ruby def trailing_zeros(n) return 0 if n.zero? (n ^ (n - 1)).bit_length - 1 end ``` ---------------------------------------- Feature #20163: Introduce #bit_count method on Integer https://bugs.ruby-lang.org/issues/20163#change-117952 * 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 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 -- https://bugs.ruby-lang.org/