Skip to content

Commit da3551c

Browse files
committed
pythongh-119714: Add PyLong_GetNumBits() function
1 parent cd11ff1 commit da3551c

7 files changed

Lines changed: 87 additions & 14 deletions

File tree

‎Doc/c-api/long.rst‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -494,6 +494,18 @@ distinguished from a number. Use :c:func:`PyErr_Occurred` to disambiguate.
494494
.. versionadded:: 3.13
495495
496496
497+
.. c:function:: Py_ssize_t PyLong_GetNumBits(PyObject *obj)
498+
499+
Get the number of bits of an integer.
500+
501+
* Return the number of bits on success: greater than or equal to zero.
502+
* Set an exception and return ``-1`` on error.
503+
* Set an :exc:`OverflowError` exception, and return ``-1`` if the number
504+
of bits doesn't fit into ``Py_ssize_t``.
505+
506+
.. versionadded:: 3.14
507+
508+
497509
.. c:function:: int PyUnstable_Long_IsCompact(const PyLongObject* op)
498510
499511
Return 1 if *op* is compact, 0 otherwise.

‎Doc/whatsnew/3.14.rst‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -225,6 +225,9 @@ C API Changes
225225
New Features
226226
------------
227227

228+
* Add :c:func:`PyLong_GetNumBits` function to get the number of bits of an
229+
integer. (Contributed by Victor Stinner in :gh:`119714`.)
230+
228231
Porting to Python 3.14
229232
----------------------
230233

‎Include/cpython/longobject.h‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -102,3 +102,6 @@ PyAPI_FUNC(int) _PyLong_AsByteArray(PyLongObject* v,
102102

103103
/* For use by the gcd function in mathmodule.c */
104104
PyAPI_FUNC(PyObject *) _PyLong_GCD(PyObject *, PyObject *);
105+
106+
// Get the number of bits of an integer
107+
PyAPI_FUNC(Py_ssize_t) PyLong_GetNumBits(PyObject *obj);

‎Lib/test/test_capi/test_long.py‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -721,6 +721,21 @@ def test_long_fromnativebytes(self):
721721
self.assertEqual(expect_u, fromnativebytes(v_be, n, 4, 1),
722722
f"PyLong_FromNativeBytes(buffer, {n}, <big|unsigned>)")
723723

724+
def test_long_getnumbits(self):
725+
numbits = _testcapi.pylong_getnumbits
726+
self.assertEqual(numbits(0), 0)
727+
self.assertEqual(numbits(7), 3)
728+
self.assertEqual(numbits(-37), 6)
729+
self.assertEqual(numbits(684_643_661_981), 40)
730+
self.assertEqual(numbits(2**123-1), 123)
731+
732+
for invalid_type in (1.0, 1j, "abc"):
733+
with self.subTest(invalid_type=invalid_type):
734+
with self.assertRaises(TypeError):
735+
numbits(invalid_type)
736+
737+
# CRASHES numbits(NULL)
738+
724739

725740
if __name__ == "__main__":
726741
unittest.main()
Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,2 @@
1+
Add :c:func:`PyLong_GetNumBits` function to get the number of bits of an
2+
integer. Patch by Victor Stinner.

‎Modules/_testcapi/long.c‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -104,12 +104,25 @@ pylong_aspid(PyObject *module, PyObject *arg)
104104
}
105105

106106

107+
static PyObject *
108+
pylong_getnumbits(PyObject *module, PyObject *arg)
109+
{
110+
NULLABLE(arg);
111+
Py_ssize_t bits = PyLong_GetNumBits(arg);
112+
if (bits < 0) {
113+
return NULL;
114+
}
115+
return PyLong_FromSsize_t(bits);
116+
}
117+
118+
107119
static PyMethodDef test_methods[] = {
108120
_TESTCAPI_CALL_LONG_COMPACT_API_METHODDEF
109121
{"pylong_fromunicodeobject", pylong_fromunicodeobject, METH_VARARGS},
110122
{"pylong_asnativebytes", pylong_asnativebytes, METH_VARARGS},
111123
{"pylong_fromnativebytes", pylong_fromnativebytes, METH_VARARGS},
112124
{"pylong_aspid", pylong_aspid, METH_O},
125+
{"pylong_getnumbits", pylong_getnumbits, METH_O},
113126
{NULL},
114127
};
115128

‎Objects/longobject.c‎

Lines changed: 39 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -780,28 +780,32 @@ bit_length_digit(digit x)
780780
return _Py_bit_length((unsigned long)x);
781781
}
782782

783+
783784
size_t
784785
_PyLong_NumBits(PyObject *vv)
785786
{
786787
PyLongObject *v = (PyLongObject *)vv;
787-
size_t result = 0;
788-
Py_ssize_t ndigits;
789-
int msd_bits;
790-
791788
assert(v != NULL);
792789
assert(PyLong_Check(v));
793-
ndigits = _PyLong_DigitCount(v);
790+
791+
Py_ssize_t ndigits = _PyLong_DigitCount(v);
794792
assert(ndigits == 0 || v->long_value.ob_digit[ndigits - 1] != 0);
795-
if (ndigits > 0) {
796-
digit msd = v->long_value.ob_digit[ndigits - 1];
797-
if ((size_t)(ndigits - 1) > SIZE_MAX / (size_t)PyLong_SHIFT)
798-
goto Overflow;
799-
result = (size_t)(ndigits - 1) * (size_t)PyLong_SHIFT;
800-
msd_bits = bit_length_digit(msd);
801-
if (SIZE_MAX - msd_bits < result)
802-
goto Overflow;
803-
result += msd_bits;
793+
if (ndigits == 0) {
794+
return 0;
795+
}
796+
assert(ndigits > 0);
797+
798+
digit msd = v->long_value.ob_digit[ndigits - 1];
799+
if ((size_t)(ndigits - 1) > SIZE_MAX / (size_t)PyLong_SHIFT) {
800+
goto Overflow;
801+
}
802+
size_t result = (size_t)(ndigits - 1) * (size_t)PyLong_SHIFT;
803+
804+
int msd_bits = bit_length_digit(msd);
805+
if (SIZE_MAX - msd_bits < result) {
806+
goto Overflow;
804807
}
808+
result += msd_bits;
805809
return result;
806810

807811
Overflow:
@@ -810,6 +814,27 @@ _PyLong_NumBits(PyObject *vv)
810814
return (size_t)-1;
811815
}
812816

817+
818+
Py_ssize_t
819+
PyLong_GetNumBits(PyObject *obj)
820+
{
821+
if (!PyLong_Check(obj)) {
822+
PyErr_Format(PyExc_TypeError, "expect int, got %T", obj);
823+
return -1;
824+
}
825+
size_t bits = _PyLong_NumBits(obj);
826+
if (bits == (size_t)-1) {
827+
return -1;
828+
}
829+
if (bits > (size_t)PY_SSIZE_T_MAX) {
830+
PyErr_SetString(PyExc_OverflowError,
831+
"int has too many bits to express in Py_ssize_t");
832+
return -1;
833+
}
834+
return (Py_ssize_t)bits;
835+
}
836+
837+
813838
PyObject *
814839
_PyLong_FromByteArray(const unsigned char* bytes, size_t n,
815840
int little_endian, int is_signed)

0 commit comments

Comments
 (0)