## Feature #8738

### Integer#single_bit? (Actually Fixnum#single_bit? and Bignum#single_bit?)

Status: | Rejected | ||
---|---|---|---|

Priority: | Normal | ||

Assignee: | - |

**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?

### History

#### #1 Updated by Marcus Stollsteimer over 2 years ago

Regarding the naming, I find

8.single_bit? # => true

a little strange (that's 4 bits), power_of_2?/power_of_two? seem to be more to the point.

#### #2 Updated by Yukihiro Matsumoto over 2 years ago

**Status**changed from*Open*to*Feedback*

I don't see the use-case of this method. Is there any case that happens so frequently to have build-in method (maybe performance-wise)?

Matz.

#### #3 Updated by Akira Tanaka over 2 years ago

2013/8/5 stomar (Marcus Stollsteimer) redmine@ruby-lang.org:

Issue #8738 has been updated by stomar (Marcus Stollsteimer).

Regarding the naming, I find

8.single_bit? # => true

a little strange (that's 4 bits), power_of_2?/power_of_two? seem to be more to the point.

I feel power_of_two? returns false for all negative numbers.

But I want to determine negative powers of two.

So, if power_of_two? method will be added, I'd like to add

negative_power_of_two? method too.

(It returns true for -1, -2, -4, ...)

negative_power_of_two? can be combined with bit_length (absolute number) as

n.negative_power_of_two? ? n.bit_length <= 32 : n.bit_length < 32

to determine n fits in 32 bits signed integer with two's complement format.

It can be combined with bit_length (two's complement) as

n.negative_power_of_two? ? n.bit_length < 53 : n.bit_length <= 53

to determine n fits in 53 bits integer with absolute number format.

--

Tanaka Akira

#### #4 Updated by Akira Tanaka over 2 years ago

matz (Yukihiro Matsumoto) wrote:

I don't see the use-case of this method. Is there any case that happens so frequently to have build-in method (maybe performance-wise)?

My intended use case is assists Integer#bit_length to determine

an integer fits an fixed size two's complement representation.

(I assume Integer#bit_lengthworks for absolute number.)

After some code searching I found several applications.

- Some application can be faster when input is a power of two. For example, integer to string (like Integer#to_s) can be implemented specially when radix is a power of two. In such case, the method can be used to decide the special case or not.
- Some library require input size be a power of two.
So application may want to test input size.
- FFT needs input size to be a power of two.
- A function in OpenGL require image width and height to be a power of two. http://www.khronos.org/opengles/sdk/docs/man/xhtml/glGenerateMipmap.xml

- Internal buffer size, table size, etc. tend to be a power of two. So application may want to assert the size is a power of two.

Several software provides this feature.

Squeak Smalltalk has isPowerOfTwo.

http://web.cecs.pdx.edu/~black/OOP/Tutorial/Squeak%20Classes%20Ref.html#NumericClasses.NET has BigInteger.IsPowerOfTwo.

http://msdn.microsoft.com/ja-jp/library/system.numerics.biginteger.ispoweroftwo.aspxCLN has power2p.

http://www.ginac.de/CLN/cln.html#Exact-numbersNetBSD kernel has powerof2.

http://www.daemon-systems.org/man/powerof2.9.html

#### #5 Updated by Yukihiro Matsumoto about 2 years ago

**Status**changed from*Feedback*to*Rejected*

I don't see the needs to add methods to use integers as bit-arrays.

Matz.