From: Fuad Saud Date: 2013-09-23T17:21:08-03:00 Subject: [ruby-core:57338] Re: [ruby-trunk - Feature #8700] Integer#bitsize (actually Fixnum#bitsize and Bignum#bitsize) --5240a2b4_7c83e458_5614 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit Content-Disposition: inline I like it. Pretty neat for low level bit brushing stuff. -- Fuad Saud Sent with Sparrow (http://www.sparrowmailapp.com/?sig) On Saturday, August 31, 2013 at 3:47 AM, matz (Yukihiro Matsumoto) wrote: > > Issue #8700 has been updated by matz (Yukihiro Matsumoto). > > > Accepted. It should be work as 2's complement for negative numbers. > > Matz. > > ---------------------------------------- > Feature #8700: Integer#bitsize (actually Fixnum#bitsize and Bignum#bitsize) > https://bugs.ruby-lang.org/issues/8700#change-41474 > > Author: akr (Akira Tanaka) > Status: Open > Priority: Normal > Assignee: > Category: > Target version: > > > How about adding Integer#bitsize (actually Fixnum#bitsize and Bignum#bitsize)? > > Integer#bitsize returns the position of the most significant bit in the absolute value. > (The position of the least significant bit is 1.) > It returns 0 if no bit set (i.e. the value 0). > > Mathematically, n.bitsize is ceil(log2(abs(n)+1)). > > Sometimes we want to know the size of a integer. > > * Determine the size of an integer in some format. > Although there are various formats, bitsize is a key property to determine the result size. > Several examples: > * If a format is 4 bytes for absolute value, it overflows if 32 <= n.bitsize. > * If a format is 4 bytes for sign bit with absolute value, it overflows if 31 <= n.bitsize. > * If a format is 4 bytes for 2's complement format, it overflow if 31 <= n.bitsize && n != -2**31. > * BER-compressed integer needs (n.bitsize+6)/7 bytes when n > 0. > BER-compressed integer is an example of VLQ. > http://en.wikipedia.org/wiki/Variable-length_quantity > * Elias gamma coding needs 2*n.bitsize-1 bits. > https://en.wikipedia.org/wiki/Elias_gamma_coding > * Elias delta coding needs 2*n.bitsize.bitsize+n.bitsize-2 bits. > https://en.wikipedia.org/wiki/Elias_delta_coding > > * bitsize may be used to estimate the time or space cost of an algorithm. > For example, the result size of integer multiplication, x*y, is x.bitsize + y.bitsize. > The number of comparisons of binary search is sorted_array.length.bitsize, etc. > This is because n.bitsize is an approximation of log2(abs(n)). > So Math.log2 can be used for this purpose too. > However bitsize may be preferable if floating point error is not desirable. > > There are several software which has similar feature. > > * Python 3.1 has int.bit_length(). > http://docs.python.org/dev/library/stdtypes.html > http://docs.python.org/3.1/whatsnew/3.1.html > http://bugs.python.org/issue3439 > > * Java java.math.BigInteger has bitLength() method. > http://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html#bitLength() > > * Mathematica has BitLength. > http://reference.wolfram.com/mathematica/ref/BitLength.html > > * GMP has mpz_sizeinbase(n, base). > http://gmplib.org/manual/Miscellaneous-Integer-Functions.html > > * NetBSD 5.0 has ilog2(). > http://netbsd.gw.com/cgi-bin/man-cgi?ilog2++NetBSD-6.0 > > I think there are two concerns for this issue. > * method name > * behavior for zero and negative number > > I named the method as bitsize, mainly because > there is Fixnum#size and Bignum#size. > However I'm open for other names such as: > * bitlength > * numbits > * ilog2 > * maxbit > Some names may suggest different behavior, though. > > The behavior for zero and negative number is not trivial. > > Python adopts ceil(log2(abs(n)+1)) but > Java and Mathematica adopts ceil(log2(n < 0 ? -n : n+1)). > The difference is absolute number v.s. 2's complement number. > > Some people may prefer ilog2, which name suggests ilog2(0) raise an error. > > I choose ceil(log2(abs(n)+1)). (i.e. absolute number, same as Python). > I think absolute number is easier to understand than 2's complement for many people. > > I attached the implementation as bitsize.patch. > The patch implements both Bignum#bitsize and Fixnum#bitsize in bignum.c. > It is because Fixnum#bitsize uses bitsize macro and it is defined in bignum.c. > Maybe, the macro should be moved to internal.h and the implementation of > Fixnum#bitsize should be moved to numeric.c. > > Any comments? > > > > -- > http://bugs.ruby-lang.org/ > > --5240a2b4_7c83e458_5614 Content-Type: text/html; charset="utf-8" Content-Transfer-Encoding: quoted-printable Content-Disposition: inline
I like it. Pretty neat for low level bit brushing stuff.

-- 
=46uad Saud
Sent with S= parrow

=20

On Saturday, August 31= , 2013 at 3:47 AM, matz (Yukihiro Matsumoto) wrote:


Issue =238700 has= been updated by matz (Yukihiro Matsumoto).


=
Accepted. It should be work as 2's complement for negative nu= mbers.

Matz.

----------= ------------------------------
=46eature =238700: Integer=23bit= size (actually =46ixnum=23bitsize and Bignum=23bitsize)

= Author: akr (Akira Tanaka)
Status: Open
Priority: Nor= mal
Assignee:
Category:
Target version: <= /div>


How about adding Integer=23bitsiz= e (actually =46ixnum=23bitsize and Bignum=23bitsize)=3F

Integer=23bitsize returns the position of the most significant bi= t in the absolute value.
(The position of the least significant= bit is 1.)
It returns 0 if no bit set (i.e. the value 0).

Mathematically, n.bitsize is ceil(log2(abs(n)+1)).

Sometimes we want to know the size of a integer.<= /div>

* Determine the size of an integer in some forma= t.
Although there are various formats, bitsize is a key prope= rty to determine the result size.
Several examples:
* If a format is 4 bytes for absolute value, it overflows if 32 <=3D= n.bitsize.
* If a format is 4 bytes for sign bit with absolu= te value, it overflows if 31 <=3D n.bitsize.
* If a format= is 4 bytes for 2's complement format, it overflow if 31 <=3D n.bitsiz= e && n =21=3D -2**31.
* BER-compressed integer needs = (n.bitsize+6)/7 bytes when n > 0.
BER-compressed integer= is an example of VLQ.
* Elias gamma coding needs 2*n.bitsize= -1 bits.
https://en.wikipedia.org/wiki/Elias=5Fdelta=5Fcoding<= /div>

* bitsize may be used to estimate the time or sp= ace cost of an algorithm.
=46or example, the result size of i= nteger multiplication, x*y, is x.bitsize + y.bitsize.
The num= ber of comparisons of binary search is sorted=5Farray.length.bitsize, etc= .
This is because n.bitsize is an approximation of log2(abs(n= )).
So Math.log2 can be used for this purpose too.
= However bitsize may be preferable if floating point error is not desira= ble.

There are several software which has simila= r feature.

* Python 3.1 has int.bit=5Flength().<= /div>

<= /div>
* Java java.math.BigInteger has bitLength() method.

* Mathematic= a has BitLength.

* GMP has mpz=5Fsizeinbas= e(n, base).

* NetBSD 5.0 has ilog2= ().







=20 =20 =20 =20
=20

--5240a2b4_7c83e458_5614--