Issue #3439: add bit_length method to int and long.
Thanks Fredrik Johansson and Victor Stinner for code,
Raymond Hettinger for review.
diff --git a/Objects/intobject.c b/Objects/intobject.c
index e73c921..9baee8e 100644
--- a/Objects/intobject.c
+++ b/Objects/intobject.c
@@ -1138,6 +1138,40 @@
return NULL;
}
+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 *
+int_bit_length(PyIntObject *v)
+{
+ unsigned long n;
+ long r = 0;
+
+ if (v->ob_ival < 0)
+ /* avoid undefined behaviour when v->ob_ival == -LONG_MAX-1 */
+ n = 0U-(unsigned long)v->ob_ival;
+ else
+ n = (unsigned long)v->ob_ival;
+
+ while (n >= 32) {
+ r += 6;
+ n >>= 6;
+ }
+ r += (long)(BitLengthTable[n]);
+ return PyInt_FromLong(r);
+}
+
+PyDoc_STRVAR(int_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 *
int_is_finite(PyObject *v)
@@ -1149,6 +1183,8 @@
static PyMethodDef int_methods[] = {
{"conjugate", (PyCFunction)int_int, METH_NOARGS,
"Returns self, the complex conjugate of any int."},
+ {"bit_length", (PyCFunction)int_bit_length, METH_NOARGS,
+ int_bit_length_doc},
#if 0
{"is_finite", (PyCFunction)int_is_finite, METH_NOARGS,
"Returns always True."},
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 @@
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 @@
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."},