From: "akr (Akira Tanaka)" <akr@...>
Date: 2013-08-11T22:36:52+09:00
Subject: [ruby-core:56554] [ruby-trunk - Feature #8738] Integer#single_bit?	(Actually Fixnum#single_bit? and Bignum#single_bit?)


Issue #8738 has been updated by akr (Akira Tanaka).


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.aspx

* CLN has power2p.
  http://www.ginac.de/CLN/cln.html#Exact-numbers

* NetBSD kernel has powerof2.
  http://www.daemon-systems.org/man/powerof2.9.html

----------------------------------------
Feature #8738: Integer#single_bit? (Actually Fixnum#single_bit? and Bignum#single_bit?)
https://bugs.ruby-lang.org/issues/8738#change-41092

Author: akr (Akira Tanaka)
Status: Feedback
Priority: Normal
Assignee: 
Category: 
Target version: 


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?



-- 
http://bugs.ruby-lang.org/