Feature #8738
closedInteger#single_bit? (Actually Fixnum#single_bit? and Bignum#single_bit?)
Description
How about a new method Integer#single_bit?
(Actually Fixnum#single_bit? and Bignum#single_bit?)
n.single_bit? returns true for abs(n) is 1, 2, 4, ..., 2**i for some i.
Sometimes we need to test an integer contains only one bit or not.
It can be written as x != 0 && (x.abs & (x.abs-1)) == 0 but it is not
so easy to understand and it needs several Bignum allocations if x is Bignum.
I propose this method mainly because it assists
Integer#bit_length to determine an integer fits in a fixed size
two's complement format.
If Integer#bit_length works for abs(n) as I proposed as [Feature #8700],
-2**m should be tested for two's complement format and
Integer#single_bit? can be used for that without
Bignum allocation.
(If Integer#bit_length works for two's complement number as Java,
Integer#single_bit? can be used to test abs(n).bit_length without Bignum
allocation. Integer#single_bit? is useful anyway.)
Integer#single_bit? has other use cases.
Some algorithms can be simplified if an input is a power of two.
For example, multiplication and division can be a bit shift.
Another example, FFT require input size is a power of two.
I think it can be used for various applications because
powers of two are special numbers for binary computer.
Several considerations:
There are several method names I considered.
- single_bit?
- power_of_two?
- power_of_2?
- pow2?
I feel power_of_two? returns false for negative numbers: (-1).power_of_two? => false.
So I choose single_bit?.
This method should behave for an absolute number
because I want to test -2**m.
I'd like to avoid n.abs.single_bit? because n.abs can allocate
a Bignum object.
I considered Integer#popcount which returns number of one bits in abs(n).
n.single_bit? can be implemented as n.popcount == 1.
I think Integer#popcount is interesting and good to have.
However Integer#single_bit? can be faster because it can return false
when it finds second one bit.
Also, n.popcount may need to allocate a Bignum if n is very big.
(n.bit_length also needs a Bignum allocation in such case, though.)
Any comments?
Files