diff options
Diffstat (limited to 'Objects/longobject.c')
| -rw-r--r-- | Objects/longobject.c | 71 |
1 files changed, 71 insertions, 0 deletions
diff --git a/Objects/longobject.c b/Objects/longobject.c index 6513069..ad5557b 100644 --- a/Objects/longobject.c +++ b/Objects/longobject.c @@ -3451,6 +3451,75 @@ long_sizeof(PyLongObject *v) return PyInt_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 PyInt_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 PyInt_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, +"long.bit_length() -> int or long\n\ +\n\ +Number of bits necessary to represent self in binary.\n\ +>>> bin(37L)\n\ +'0b100101'\n\ +>>> (37L).bit_length()\n\ +6"); + #if 0 static PyObject * long_is_finite(PyObject *v) @@ -3462,6 +3531,8 @@ long_is_finite(PyObject *v) static PyMethodDef long_methods[] = { {"conjugate", (PyCFunction)long_long, METH_NOARGS, "Returns self, the complex conjugate of any long."}, + {"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."}, |