Issue #3439: add bit_length method to int and long.

Thanks Fredrik Johansson and Victor Stinner for code,
Raymond Hettinger for review.

1 files changed, 35 insertions, 0 deletions

diff --git a/Lib/test/test_int.py b/Lib/test/test_int.py
index a2dc85f..ce18ad2 100644
--- a/Lib/test/test_int.py
+++ b/Lib/test/test_int.py
@@ -2,6 +2,7 @@ import sys
 
 import unittest
 from test.test_support import run_unittest, have_unicode
+import math
 
 L = [
         ('0', 0),
@@ -240,6 +241,40 @@ class IntTestCases(unittest.TestCase):
         self.assertEqual(int('2br45qc', 35), 4294967297L)
         self.assertEqual(int('1z141z5', 36), 4294967297L)
 
+    def test_bit_length(self):
+        tiny = 1e-10
+        for x in xrange(-65000, 65000):
+            k = x.bit_length()
+            # Check equivalence with Python version
+            self.assertEqual(k, len(bin(x).lstrip('-0b')))
+            # Behaviour as specified in the docs
+            if x != 0:
+                self.assert_(2**(k-1) <= abs(x) < 2**k)
+            else:
+                self.assertEqual(k, 0)
+            # Alternative definition: x.bit_length() == 1 + floor(log_2(x))
+            if x != 0:
+                # When x is an exact power of 2, numeric errors can
+                # cause floor(log(x)/log(2)) to be one too small; for
+                # small x this can be fixed by adding a small quantity
+                # to the quotient before taking the floor.
+                self.assertEqual(k, 1 + math.floor(
+                        math.log(abs(x))/math.log(2) + tiny))
+
+        self.assertEqual((0).bit_length(), 0)
+        self.assertEqual((1).bit_length(), 1)
+        self.assertEqual((-1).bit_length(), 1)
+        self.assertEqual((2).bit_length(), 2)
+        self.assertEqual((-2).bit_length(), 2)
+        for i in [2, 3, 15, 16, 17, 31, 32, 33, 63, 64]:
+            a = 2**i
+            self.assertEqual((a-1).bit_length(), i)
+            self.assertEqual((1-a).bit_length(), i)
+            self.assertEqual((a).bit_length(), i+1)
+            self.assertEqual((-a).bit_length(), i+1)
+            self.assertEqual((a+1).bit_length(), i+1)
+            self.assertEqual((-a-1).bit_length(), i+1)
+
     def test_intconversion(self):
         # Test __int__()
         class ClassicMissingMethods: