bpo-29882: Add an efficient popcount method for integers (#771)
* bpo-29882: Add an efficient popcount method for integers
* Update 'sign bit' and versionadded in docs
* Add entry to whatsnew document
* Doc: use positive example, mention population count
* Minor cleanups of the core code
* Move popcount_digit closer to where it's used
* Use z instead of self after conversion
* Add 'absolute value' and 'population count' to docstring
* Fix clinic error about missing summary line
* Ensure popcount_digit is portable with 64-bit ints
Co-authored-by: Mark Dickinson <dickinsm@gmail.com>
diff --git a/Objects/longobject.c b/Objects/longobject.c
index 4ae17c9..0b209a4 100644
--- a/Objects/longobject.c
+++ b/Objects/longobject.c
@@ -5304,6 +5304,75 @@
return NULL;
}
+static int
+popcount_digit(digit d)
+{
+ /* 32bit SWAR popcount. */
+ uint32_t u = d;
+ u -= (u >> 1) & 0x55555555U;
+ u = (u & 0x33333333U) + ((u >> 2) & 0x33333333U);
+ u = (u + (u >> 4)) & 0x0f0f0f0fU;
+ return (uint32_t)(u * 0x01010101U) >> 24;
+}
+
+/*[clinic input]
+int.bit_count
+
+Number of ones in the binary representation of the absolute value of self.
+
+Also known as the population count.
+
+>>> bin(13)
+'0b1101'
+>>> (13).bit_count()
+3
+[clinic start generated code]*/
+
+static PyObject *
+int_bit_count_impl(PyObject *self)
+/*[clinic end generated code: output=2e571970daf1e5c3 input=7e0adef8e8ccdf2e]*/
+{
+ assert(self != NULL);
+ assert(PyLong_Check(self));
+
+ PyLongObject *z = (PyLongObject *)self;
+ Py_ssize_t ndigits = Py_ABS(Py_SIZE(z));
+ Py_ssize_t bit_count = 0;
+
+ /* Each digit has up to PyLong_SHIFT ones, so the accumulated bit count
+ from the first PY_SSIZE_T_MAX/PyLong_SHIFT digits can't overflow a
+ Py_ssize_t. */
+ Py_ssize_t ndigits_fast = Py_MIN(ndigits, PY_SSIZE_T_MAX/PyLong_SHIFT);
+ for (Py_ssize_t i = 0; i < ndigits_fast; i++) {
+ bit_count += popcount_digit(z->ob_digit[i]);
+ }
+
+ PyObject *result = PyLong_FromSsize_t(bit_count);
+ if (result == NULL) {
+ return NULL;
+ }
+
+ /* Use Python integers if bit_count would overflow. */
+ for (Py_ssize_t i = ndigits_fast; i < ndigits; i++) {
+ PyObject *x = PyLong_FromLong(popcount_digit(z->ob_digit[i]));
+ if (x == NULL) {
+ goto error;
+ }
+ PyObject *y = long_add((PyLongObject *)result, (PyLongObject *)x);
+ Py_DECREF(x);
+ if (y == NULL) {
+ goto error;
+ }
+ Py_DECREF(result);
+ result = y;
+ }
+
+ return result;
+
+ error:
+ Py_DECREF(result);
+ return NULL;
+}
/*[clinic input]
int.as_integer_ratio
@@ -5460,6 +5529,7 @@
{"conjugate", long_long_meth, METH_NOARGS,
"Returns self, the complex conjugate of any int."},
INT_BIT_LENGTH_METHODDEF
+ INT_BIT_COUNT_METHODDEF
INT_TO_BYTES_METHODDEF
INT_FROM_BYTES_METHODDEF
INT_AS_INTEGER_RATIO_METHODDEF