[前][次][番号順一覧][スレッド一覧]

ruby-changes:30667

From: akr <ko1@a...>
Date: Sun, 1 Sep 2013 00:09:27 +0900 (JST)
Subject: [ruby-changes:30667] akr:r42746 (trunk): * bignum.c (rb_big_bit_length): New method.

akr	2013-09-01 00:09:20 +0900 (Sun, 01 Sep 2013)

  New Revision: 42746

  http://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=rev&revision=42746

  Log:
    * bignum.c (rb_big_bit_length): New method.
      (rb_fix_bit_length): Ditto.
      [ruby-core:56247] [Feature #8700]

  Modified files:
    trunk/ChangeLog
    trunk/bignum.c
    trunk/test/ruby/test_integer.rb
Index: ChangeLog
===================================================================
--- ChangeLog	(revision 42745)
+++ ChangeLog	(revision 42746)
@@ -1,3 +1,9 @@ https://github.com/ruby/ruby/blob/trunk/ChangeLog#L1
+Sun Sep  1 00:07:09 2013  Tanaka Akira  <akr@f...>
+
+	* bignum.c (rb_big_bit_length): New method.
+	  (rb_fix_bit_length): Ditto.
+	  [ruby-core:56247] [Feature #8700]
+
 Sat Aug 31 22:18:29 2013  Tanaka Akira  <akr@f...>
 
 	* process.c (rb_clock_getres): New method.
Index: bignum.c
===================================================================
--- bignum.c	(revision 42745)
+++ bignum.c	(revision 42746)
@@ -6662,6 +6662,113 @@ rb_big_size(VALUE big) https://github.com/ruby/ruby/blob/trunk/bignum.c#L6662
 
 /*
  *  call-seq:
+ *     int.bit_length -> integer
+ *
+ *  Returns the number of bits of the value of <i>int</i>.
+ *
+ *  "the number of bits" means that
+ *  the bit position of the highest bit which is different to the sign bit.
+ *  (The bit position of the bit 2**n is n+1.)
+ *  If there is no such bit (zero or minus one), zero is returned.
+ *
+ *     (-2**10000-1).bit_length  #=> 10001
+ *     (-2**10000).bit_length    #=> 10000
+ *     (-2**10000+1).bit_length  #=> 10000
+ *
+ *     (-2**1000-1).bit_length   #=> 1001
+ *     (-2**1000).bit_length     #=> 1000
+ *     (-2**1000+1).bit_length   #=> 1000
+ *
+ *     (2**1000-1).bit_length    #=> 1000
+ *     (2**1000).bit_length      #=> 1001
+ *     (2**1000+1).bit_length    #=> 1001
+ *
+ *     (2**10000-1).bit_length   #=> 10000
+ *     (2**10000).bit_length     #=> 10001
+ *     (2**10000+1).bit_length   #=> 10001
+ *
+ */
+
+static VALUE
+rb_big_bit_length(VALUE big)
+{
+    int nlz_bits;
+    size_t numbytes;
+
+    static const BDIGIT char_bit[1] = { CHAR_BIT };
+    BDIGIT numbytes_bary[bdigit_roomof(sizeof(size_t))];
+    BDIGIT nlz_bary[1];
+    BDIGIT result_bary[bdigit_roomof(sizeof(size_t)+1)];
+
+    numbytes = rb_absint_size(big, &nlz_bits);
+
+    if (numbytes == 0)
+        return LONG2FIX(0);
+
+    if (RBIGNUM_NEGATIVE_P(big) && rb_absint_singlebit_p(big)) {
+        if (nlz_bits != CHAR_BIT-1) {
+            nlz_bits++;
+        }
+        else {
+            nlz_bits = 0;
+            numbytes--;
+        }
+    }
+
+    if (numbytes <= SIZE_MAX / CHAR_BIT) {
+        return SIZET2NUM(numbytes * CHAR_BIT - nlz_bits);
+    }
+
+    nlz_bary[0] = nlz_bits;
+
+    bary_unpack(BARY_ARGS(numbytes_bary), &numbytes, 1, sizeof(numbytes), 0,
+            INTEGER_PACK_NATIVE_BYTE_ORDER);
+    BARY_SHORT_MUL(result_bary, numbytes_bary, char_bit);
+    BARY_SUB(result_bary, result_bary, nlz_bary);
+
+    return rb_integer_unpack(result_bary, numberof(result_bary), sizeof(BDIGIT), 0,
+            INTEGER_PACK_LSWORD_FIRST|INTEGER_PACK_NATIVE_BYTE_ORDER);
+}
+
+/*
+ *  call-seq:
+ *     int.bit_length -> integer
+ *
+ *  Returns the number of bits of the value of <i>int</i>.
+ *
+ *  "the number of bits" means that
+ *  the bit position of the highest bit which is different to the sign bit.
+ *  (The bit position of the bit 2**n is n+1.)
+ *  If there is no such bit (zero or minus one), zero is returned.
+ *
+ *     (-2**12-1).bit_length     #=> 13
+ *     (-2**12).bit_length       #=> 12
+ *     (-2**12+1).bit_length     #=> 12
+ *     -0x101.bit_length         #=> 9
+ *     -0x100.bit_length         #=> 8
+ *     -0xff.bit_length          #=> 8
+ *     -2.bit_length             #=> 1
+ *     -1.bit_length             #=> 0
+ *     0.bit_length              #=> 0
+ *     1.bit_length              #=> 1
+ *     0xff.bit_length           #=> 8
+ *     0x100.bit_length          #=> 9
+ *     (2**12-1).bit_length      #=> 12
+ *     (2**12).bit_length        #=> 13
+ *     (2**12+1).bit_length      #=> 13
+ */
+
+static VALUE
+rb_fix_bit_length(VALUE fix)
+{
+    long v = FIX2LONG(fix);
+    if (v < 0)
+        v = ~v;
+    return LONG2FIX(bitsize(v));
+}
+
+/*
+ *  call-seq:
  *     big.odd? -> true or false
  *
  *  Returns <code>true</code> if <i>big</i> is an odd number.
@@ -6751,8 +6858,11 @@ Init_Bignum(void) https://github.com/ruby/ruby/blob/trunk/bignum.c#L6858
     rb_define_method(rb_cBignum, "abs", rb_big_abs, 0);
     rb_define_method(rb_cBignum, "magnitude", rb_big_abs, 0);
     rb_define_method(rb_cBignum, "size", rb_big_size, 0);
+    rb_define_method(rb_cBignum, "bit_length", rb_big_bit_length, 0);
     rb_define_method(rb_cBignum, "odd?", rb_big_odd_p, 0);
     rb_define_method(rb_cBignum, "even?", rb_big_even_p, 0);
 
+    rb_define_method(rb_cFixnum, "bit_length", rb_fix_bit_length, 0);
+
     power_cache_init();
 }
Index: test/ruby/test_integer.rb
===================================================================
--- test/ruby/test_integer.rb	(revision 42745)
+++ test/ruby/test_integer.rb	(revision 42746)
@@ -241,4 +241,40 @@ class TestInteger < Test::Unit::TestCase https://github.com/ruby/ruby/blob/trunk/test/ruby/test_integer.rb#L241
     end
     assert_equal(3 ^ 10, 3 ^ obj)
   end
+
+  def test_bit_length
+    assert_equal(13, (-2**12-1).bit_length)
+    assert_equal(12, (-2**12).bit_length)
+    assert_equal(12, (-2**12+1).bit_length)
+    assert_equal(9, -0x101.bit_length)
+    assert_equal(8, -0x100.bit_length)
+    assert_equal(8, -0xff.bit_length)
+    assert_equal(1, -2.bit_length)
+    assert_equal(0, -1.bit_length)
+    assert_equal(0, 0.bit_length)
+    assert_equal(1, 1.bit_length)
+    assert_equal(8, 0xff.bit_length)
+    assert_equal(9, 0x100.bit_length)
+    assert_equal(9, 0x101.bit_length)
+    assert_equal(12, (2**12-1).bit_length)
+    assert_equal(13, (2**12).bit_length)
+    assert_equal(13, (2**12+1).bit_length)
+
+    assert_equal(10001, (-2**10000-1).bit_length)
+    assert_equal(10000, (-2**10000).bit_length)
+    assert_equal(10000, (-2**10000+1).bit_length)
+    assert_equal(10000, (2**10000-1).bit_length)
+    assert_equal(10001, (2**10000).bit_length)
+    assert_equal(10001, (2**10000+1).bit_length)
+
+    2.upto(1000) {|i|
+      n = 2**i
+      assert_equal(i+1, (-n-1).bit_length, "(#{-n-1}).bit_length")
+      assert_equal(i,   (-n).bit_length, "(#{-n}).bit_length")
+      assert_equal(i,   (-n+1).bit_length, "(#{-n+1}).bit_length")
+      assert_equal(i,   (n-1).bit_length, "#{n-1}.bit_length")
+      assert_equal(i+1, (n).bit_length, "#{n}.bit_length")
+      assert_equal(i+1, (n+1).bit_length, "#{n+1}.bit_length")
+    }
+  end
 end

--
ML: ruby-changes@q...
Info: http://www.atdot.net/~ko1/quickml/

[前][次][番号順一覧][スレッド一覧]