[Python-checkins] r67824 - in python/branches/py3k: Doc/library/stdtypes.rst Doc/whatsnew/2.7.rst Doc/whatsnew/3.1.rst Lib/test/test_long.py Misc/ACKS Misc/NEWS Objects/longobject.c
mark.dickinson
python-checkins at python.org
Wed Dec 17 17:19:08 CET 2008
Author: mark.dickinson
Date: Wed Dec 17 17:19:07 2008
New Revision: 67824
Log:
Forward merge of r67822 to py3k: add bit_length method to int.
Modified:
python/branches/py3k/Doc/library/stdtypes.rst
python/branches/py3k/Doc/whatsnew/2.7.rst
python/branches/py3k/Doc/whatsnew/3.1.rst
python/branches/py3k/Lib/test/test_long.py
python/branches/py3k/Misc/ACKS
python/branches/py3k/Misc/NEWS
python/branches/py3k/Objects/longobject.c
Modified: python/branches/py3k/Doc/library/stdtypes.rst
==============================================================================
--- python/branches/py3k/Doc/library/stdtypes.rst (original)
+++ python/branches/py3k/Doc/library/stdtypes.rst Wed Dec 17 17:19:07 2008
@@ -419,6 +419,40 @@
overflow check.
+Additional Methods on Integer Types
+-----------------------------------
+
+.. method:: int.bit_length()
+
+ For any integer ``x``, ``x.bit_length()`` returns the number of
+ bits necessary to represent ``x`` in binary, excluding the sign
+ and any leading zeros::
+
+ >>> n = 37
+ >>> bin(n)
+ '0b100101'
+ >>> n.bit_length()
+ 6
+ >>> n = -0b00011010
+ >>> n.bit_length()
+ 5
+
+ More precisely, if ``x`` is nonzero then ``x.bit_length()`` is the
+ unique positive integer ``k`` such that ``2**(k-1) <= abs(x) <
+ 2**k``. Equivalently, ``x.bit_length()`` is equal to ``1 +
+ floor(log(x, 2))`` [#]_ . If ``x`` is zero then ``x.bit_length()``
+ gives ``0``.
+
+ Equivalent to::
+
+ def bit_length(self):
+ 'Number of bits necessary to represent self in binary.'
+ return len(bin(self).lstrip('-0b'))
+
+
+ .. versionadded:: 3.1
+
+
Additional Methods on Float
---------------------------
@@ -2639,6 +2673,11 @@
.. [#] As a consequence, the list ``[1, 2]`` is considered equal to ``[1.0, 2.0]``, and
similarly for tuples.
+.. [#] Beware of this formula! It's mathematically valid, but as a
+ Python expression it will not give correct results for all ``x``,
+ as a consequence of the limited precision of floating-point
+ arithmetic.
+
.. [#] They must have since the parser can't tell the type of the operands.
.. [#] To format only a tuple you should therefore provide a singleton tuple whose only
Modified: python/branches/py3k/Doc/whatsnew/2.7.rst
==============================================================================
--- python/branches/py3k/Doc/whatsnew/2.7.rst (original)
+++ python/branches/py3k/Doc/whatsnew/2.7.rst Wed Dec 17 17:19:07 2008
@@ -66,7 +66,23 @@
Some smaller changes made to the core Python language are:
-* List of changes to be written here.
+* The :func:`int` and :func:`long` types gained a ``bit_length``
+ method that returns the number of bits necessary to represent
+ its argument in binary::
+
+ >>> n = 37
+ >>> bin(37)
+ '0b100101'
+ >>> n.bit_length()
+ 6
+ >>> n = 2**123-1
+ >>> n.bit_length()
+ 123
+ >>> (n+1).bit_length()
+ 124
+
+ (Contributed by Fredrik Johansson and Victor Stinner; :issue:`3439`.)
+
.. ======================================================================
Modified: python/branches/py3k/Doc/whatsnew/3.1.rst
==============================================================================
--- python/branches/py3k/Doc/whatsnew/3.1.rst (original)
+++ python/branches/py3k/Doc/whatsnew/3.1.rst Wed Dec 17 17:19:07 2008
@@ -66,4 +66,26 @@
.. ======================================================================
+Other Language Changes
+======================
+
+Some smaller changes made to the core Python language are:
+
+* The :func:`int` type gained a ``bit_length`` method that returns the
+ number of bits necessary to represent its argument in binary::
+
+ >>> n = 37
+ >>> bin(37)
+ '0b100101'
+ >>> n.bit_length()
+ 6
+ >>> n = 2**123-1
+ >>> n.bit_length()
+ 123
+ >>> (n+1).bit_length()
+ 124
+
+ (Contributed by Fredrik Johansson and Victor Stinner; :issue:`3439`.)
+
+
.. ======================================================================
Modified: python/branches/py3k/Lib/test/test_long.py
==============================================================================
--- python/branches/py3k/Lib/test/test_long.py (original)
+++ python/branches/py3k/Lib/test/test_long.py Wed Dec 17 17:19:07 2008
@@ -3,6 +3,7 @@
import sys
import random
+import math
# Used for lazy formatting of failure messages
class Frm(object):
@@ -836,6 +837,41 @@
self.assertTrue(i - i is 0)
self.assertTrue(0 * i is 0)
+ def test_bit_length(self):
+ tiny = 1e-10
+ for x in range(-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, 234]:
+ 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_main():
support.run_unittest(LongTest)
Modified: python/branches/py3k/Misc/ACKS
==============================================================================
--- python/branches/py3k/Misc/ACKS (original)
+++ python/branches/py3k/Misc/ACKS Wed Dec 17 17:19:07 2008
@@ -344,6 +344,7 @@
Flemming Kjær Jensen
Jiba
Orjan Johansen
+Fredrik Johansson
Gregory K. Johnson
Simon Johnston
Evan Jones
Modified: python/branches/py3k/Misc/NEWS
==============================================================================
--- python/branches/py3k/Misc/NEWS (original)
+++ python/branches/py3k/Misc/NEWS Wed Dec 17 17:19:07 2008
@@ -12,6 +12,8 @@
Core and Builtins
-----------------
+- Issue #3439: Add a bit_length method to int.
+
- Issue #2173: When getting device encoding, check that return value of
nl_langinfo is not the empty string. This was causing silent build
failures on OS X.
Modified: python/branches/py3k/Objects/longobject.c
==============================================================================
--- python/branches/py3k/Objects/longobject.c (original)
+++ python/branches/py3k/Objects/longobject.c Wed Dec 17 17:19:07 2008
@@ -3650,6 +3650,75 @@
return PyLong_FromSsize_t(res);
}
+static const unsigned char BitLengthTable[32] = {
+ 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
+ 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5
+};
+
+static PyObject *
+long_bit_length(PyLongObject *v)
+{
+ PyLongObject *result, *x, *y;
+ Py_ssize_t ndigits, msd_bits = 0;
+ digit msd;
+
+ assert(v != NULL);
+ assert(PyLong_Check(v));
+
+ ndigits = ABS(Py_SIZE(v));
+ if (ndigits == 0)
+ return PyLong_FromLong(0);
+
+ msd = v->ob_digit[ndigits-1];
+ while (msd >= 32) {
+ msd_bits += 6;
+ msd >>= 6;
+ }
+ msd_bits += (long)(BitLengthTable[msd]);
+
+ if (ndigits <= PY_SSIZE_T_MAX/PyLong_SHIFT)
+ return PyLong_FromSsize_t((ndigits-1)*PyLong_SHIFT + msd_bits);
+
+ /* expression above may overflow; use Python integers instead */
+ result = (PyLongObject *)PyLong_FromSsize_t(ndigits - 1);
+ if (result == NULL)
+ return NULL;
+ x = (PyLongObject *)PyLong_FromLong(PyLong_SHIFT);
+ if (x == NULL)
+ goto error;
+ y = (PyLongObject *)long_mul(result, x);
+ Py_DECREF(x);
+ if (y == NULL)
+ goto error;
+ Py_DECREF(result);
+ result = y;
+
+ x = (PyLongObject *)PyLong_FromLong(msd_bits);
+ if (x == NULL)
+ goto error;
+ y = (PyLongObject *)long_add(result, x);
+ Py_DECREF(x);
+ if (y == NULL)
+ goto error;
+ Py_DECREF(result);
+ result = y;
+
+ return (PyObject *)result;
+
+error:
+ Py_DECREF(result);
+ return NULL;
+}
+
+PyDoc_STRVAR(long_bit_length_doc,
+"int.bit_length() -> int\n\
+\n\
+Number of bits necessary to represent self in binary.\n\
+>>> bin(37)\n\
+'0b100101'\n\
+>>> (37).bit_length()\n\
+6");
+
#if 0
static PyObject *
long_is_finite(PyObject *v)
@@ -3661,6 +3730,8 @@
static PyMethodDef long_methods[] = {
{"conjugate", (PyCFunction)long_long, METH_NOARGS,
"Returns self, the complex conjugate of any int."},
+ {"bit_length", (PyCFunction)long_bit_length, METH_NOARGS,
+ long_bit_length_doc},
#if 0
{"is_finite", (PyCFunction)long_is_finite, METH_NOARGS,
"Returns always True."},
More information about the Python-checkins
mailing list