diff options
| -rw-r--r-- | Doc/library/stdtypes.rst | 39 | ||||
| -rw-r--r-- | Doc/whatsnew/2.7.rst | 18 | ||||
| -rw-r--r-- | Doc/whatsnew/3.1.rst | 22 | ||||
| -rw-r--r-- | Lib/test/test_long.py | 36 | ||||
| -rw-r--r-- | Misc/ACKS | 1 | ||||
| -rw-r--r-- | Misc/NEWS | 2 | ||||
| -rw-r--r-- | Objects/longobject.c | 71 |
7 files changed, 188 insertions, 1 deletions
diff --git a/Doc/library/stdtypes.rst b/Doc/library/stdtypes.rst index 68e8dba..638bafd 100644 --- a/Doc/library/stdtypes.rst +++ b/Doc/library/stdtypes.rst @@ -419,6 +419,40 @@ Notes: 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 @@ types, where they are relevant. Some of these are not reported by the .. [#] 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 diff --git a/Doc/whatsnew/2.7.rst b/Doc/whatsnew/2.7.rst index a9eb0ba..61084c8 100644 --- a/Doc/whatsnew/2.7.rst +++ b/Doc/whatsnew/2.7.rst @@ -66,7 +66,23 @@ Other Language Changes 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`.) + .. ====================================================================== diff --git a/Doc/whatsnew/3.1.rst b/Doc/whatsnew/3.1.rst index a244568..7df4d1e 100644 --- a/Doc/whatsnew/3.1.rst +++ b/Doc/whatsnew/3.1.rst @@ -66,4 +66,26 @@ This article explains the new features in Python 3.1, compared to 3.0. .. ====================================================================== +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`.) + + .. ====================================================================== diff --git a/Lib/test/test_long.py b/Lib/test/test_long.py index a1db26a..cbd0b2b 100644 --- a/Lib/test/test_long.py +++ b/Lib/test/test_long.py @@ -3,6 +3,7 @@ from test import support import sys import random +import math # Used for lazy formatting of failure messages class Frm(object): @@ -836,6 +837,41 @@ class LongTest(unittest.TestCase): 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) @@ -344,6 +344,7 @@ Drew Jenkins Flemming Kjær Jensen Jiba Orjan Johansen +Fredrik Johansson Gregory K. Johnson Simon Johnston Evan Jones @@ -12,6 +12,8 @@ What's New in Python 3.1 alpha 0 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. diff --git a/Objects/longobject.c b/Objects/longobject.c index c28fe0a..677221a 100644 --- a/Objects/longobject.c +++ b/Objects/longobject.c @@ -3650,6 +3650,75 @@ long_sizeof(PyLongObject *v) 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 @@ long_is_finite(PyObject *v) 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."}, |