Feature #8738

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

Added by Akira Tanaka 9 months ago. Updated 8 months ago.

[ruby-core:56389]
Status:Rejected
Priority:Normal
Assignee:-
Category:-
Target version:-

Description

How about a new method Integer#singlebit?
(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#bitlength 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#singlebit? can be used for that without
Bignum allocation.
(If Integer#bit
length works for two's complement number as Java,
Integer#singlebit? can be used to test abs(n).bitlength 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.
* singlebit?
* power
oftwo?
* power
of2?
* pow2?
I feel power
oftwo? returns false for negative numbers: (-1).poweroftwo? => 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.singlebit? 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?

single_bit_p.patch Magnifier (4.64 KB) Akira Tanaka, 08/05/2013 10:03 PM

History

#1 Updated by Marcus Stollsteimer 9 months ago

Regarding the naming, I find

8.single_bit? # => true

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

#2 Updated by Yukihiro Matsumoto 8 months 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 8 months 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), powerof2?/poweroftwo? seem to be more to the point.

I feel poweroftwo? returns false for all negative numbers.
But I want to determine negative powers of two.

So, if poweroftwo? method will be added, I'd like to add
negativepowerof_two? method too.
(It returns true for -1, -2, -4, ...)

negativepoweroftwo? can be combined with bitlength (absolute number) as
n.negativepoweroftwo? ? n.bitlength <= 32 : n.bit_length < 32
to determine n fits in 32 bits signed integer with two's complement format.

It can be combined with bitlength (two's complement) as
n.negative
poweroftwo? ? n.bitlength < 53 : n.bitlength <= 53
to determine n fits in 53 bits integer with absolute number format.
--
Tanaka Akira

#4 Updated by Akira Tanaka 8 months 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#bitlength 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.
  • 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.

#5 Updated by Yukihiro Matsumoto 8 months ago

  • Status changed from Feedback to Rejected

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

Matz.

Also available in: Atom PDF