gh-119714: Add PyLong_GetNumBits() function

vstinner · May 29, 2024 · May 31, 2024 · Jun 3, 2024 · Jun 3, 2024 · Jun 3, 2024
commit 0b4681745c233e1b96492493de36125defd3c0b5
@@ -507,6 +507,18 @@ distinguished from a number.  Use :c:func:`PyErr_Occurred` to disambiguate.
    .. versionadded:: 3.14
 
 
+.. c:function:: Py_ssize_t PyLong_GetNumBits(PyObject *obj)
+
+   Get the number of bits of an integer.
+
+   * Return the number of bits on success: greater than or equal to zero.
+   * Set an exception and return ``-1`` on error.
+   * Set an :exc:`OverflowError` exception, and return ``-1`` if the number
+     of bits doesn't fit into ``Py_ssize_t``.
+
+   .. versionadded:: 3.14
+
+
 .. c:function:: int PyUnstable_Long_IsCompact(const PyLongObject* op)
 
    Return 1 if *op* is compact, 0 otherwise.

@@ -258,6 +258,9 @@ New Features
 * Add :c:func:`PyLong_GetSign` function to get the sign of :class:`int` objects.
   (Contributed by Sergey B Kirpichev in :gh:`116560`.)
 
+* Add :c:func:`PyLong_GetNumBits` function to get the number of bits of an
+  integer. (Contributed by Victor Stinner in :gh:`119714`.)
+
 Porting to Python 3.14
 ----------------------
 

diff --git a/Include/cpython/longobject.h b/Include/cpython/longobject.h
@@ -115,3 +115,6 @@ PyAPI_FUNC(int) _PyLong_AsByteArray(PyLongObject* v,
 
 /* For use by the gcd function in mathmodule.c */
 PyAPI_FUNC(PyObject *) _PyLong_GCD(PyObject *, PyObject *);
+
+// Get the number of bits of an integer
+PyAPI_FUNC(Py_ssize_t) PyLong_GetNumBits(PyObject *obj);
diff --git a/Lib/test/test_capi/test_long.py b/Lib/test/test_capi/test_long.py
@@ -737,6 +737,21 @@ def test_long_getsign(self):
 
         # CRASHES getsign(NULL)
 
+    def test_long_getnumbits(self):
+        numbits = _testcapi.pylong_getnumbits
+        self.assertEqual(numbits(0), 0)
+        self.assertEqual(numbits(7), 3)
+        self.assertEqual(numbits(-37), 6)
+        self.assertEqual(numbits(684_643_661_981), 40)
+        self.assertEqual(numbits(2**123-1), 123)
+
+        for invalid_type in (1.0, 1j, "abc"):
+            with self.subTest(invalid_type=invalid_type):
+                with self.assertRaises(TypeError):
+                    numbits(invalid_type)
+
+        # CRASHES numbits(NULL)
+
 
 if __name__ == "__main__":
     unittest.main()
diff --git a/Misc/NEWS.d/next/C API/2024-05-29-11-25-26.gh-issue-119714.We9eUg.rst b/Misc/NEWS.d/next/C API/2024-05-29-11-25-26.gh-issue-119714.We9eUg.rst
@@ -0,0 +1,2 @@
+Add :c:func:`PyLong_GetNumBits` function to get the number of bits of an
+integer. Patch by Victor Stinner.
diff --git a/Modules/_testcapi/long.c b/Modules/_testcapi/long.c
@@ -117,13 +117,26 @@ pylong_aspid(PyObject *module, PyObject *arg)
 }
 
 
+static PyObject *
+pylong_getnumbits(PyObject *module, PyObject *arg)
+{
+    NULLABLE(arg);
+    Py_ssize_t bits = PyLong_GetNumBits(arg);
+    if (bits < 0) {
+        return NULL;
+    }
+    return PyLong_FromSsize_t(bits);
+}
+
+
 static PyMethodDef test_methods[] = {
     _TESTCAPI_CALL_LONG_COMPACT_API_METHODDEF
     {"pylong_fromunicodeobject",    pylong_fromunicodeobject,   METH_VARARGS},
     {"pylong_asnativebytes",        pylong_asnativebytes,       METH_VARARGS},
     {"pylong_fromnativebytes",      pylong_fromnativebytes,     METH_VARARGS},
     {"pylong_getsign",              pylong_getsign,             METH_O},
     {"pylong_aspid",                pylong_aspid,               METH_O},
+    {"pylong_getnumbits",           pylong_getnumbits,          METH_O},
     {NULL},
 };
 

diff --git a/Objects/longobject.c b/Objects/longobject.c
@@ -792,28 +792,32 @@ bit_length_digit(digit x)
     return _Py_bit_length((unsigned long)x);
 }
 
+
 size_t
 _PyLong_NumBits(PyObject *vv)
 {
     PyLongObject *v = (PyLongObject *)vv;
-    size_t result = 0;
-    Py_ssize_t ndigits;
-    int msd_bits;
-
     assert(v != NULL);
     assert(PyLong_Check(v));
-    ndigits = _PyLong_DigitCount(v);
+
+    Py_ssize_t ndigits = _PyLong_DigitCount(v);
     assert(ndigits == 0 || v->long_value.ob_digit[ndigits - 1] != 0);
-    if (ndigits > 0) {
-        digit msd = v->long_value.ob_digit[ndigits - 1];
-        if ((size_t)(ndigits - 1) > SIZE_MAX / (size_t)PyLong_SHIFT)
-            goto Overflow;
-        result = (size_t)(ndigits - 1) * (size_t)PyLong_SHIFT;
-        msd_bits = bit_length_digit(msd);
-        if (SIZE_MAX - msd_bits < result)
-            goto Overflow;
-        result += msd_bits;
+    if (ndigits == 0) {
+        return 0;
+    }
+    assert(ndigits > 0);
+
+    digit msd = v->long_value.ob_digit[ndigits - 1];
+    if ((size_t)(ndigits - 1) > SIZE_MAX / (size_t)PyLong_SHIFT) {
+        goto Overflow;
+    }
+    size_t result = (size_t)(ndigits - 1) * (size_t)PyLong_SHIFT;
+
+    int msd_bits = bit_length_digit(msd);
+    if (SIZE_MAX - msd_bits < result) {
+        goto Overflow;
     }
+    result += msd_bits;
     return result;
 
   Overflow:
@@ -822,6 +826,27 @@ _PyLong_NumBits(PyObject *vv)
     return (size_t)-1;
 }
 
+
+Py_ssize_t
+PyLong_GetNumBits(PyObject *obj)
+{
+    if (!PyLong_Check(obj)) {
+        PyErr_Format(PyExc_TypeError, "expect int, got %T", obj);
+        return -1;
+    }
+    size_t bits = _PyLong_NumBits(obj);
+    if (bits == (size_t)-1) {
+        return -1;
+    }
+    if (bits > (size_t)PY_SSIZE_T_MAX) {
+        PyErr_SetString(PyExc_OverflowError,
+                        "int has too many bits to express in Py_ssize_t");
+        return -1;
+    }
+    return (Py_ssize_t)bits;
+}
+
+
 PyObject *
 _PyLong_FromByteArray(const unsigned char* bytes, size_t n,
                       int little_endian, int is_signed)
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,2 @@
		Add :c:func:`PyLong_GetNumBits` function to get the number of bits of an
		integer. Patch by Victor Stinner.