GeezerVison

Original file line number	Diff line number	Diff line change
Expand Up		@@ -478,6 +478,27 @@ class`. In addition, it provides a few more methods:

		.. versionadded:: 3.1

		.. method:: int.bit_count()

		Return the number of ones in the binary representation of the absolute
Comment thread mdickinson marked this conversation as resolved. Resolved Uh oh! There was an error while loading. Please reload this page.
		value of the integer. This is also known as the population count.
		Example::

		>>> n = 19
		>>> bin(n)
		'0b10011'
		>>> n.bit_count()
		3
		>>> (-n).bit_count()
		3

		Equivalent to::

		def bit_count(self):
		return bin(self).count("1")

		.. versionadded:: 3.10

		.. method:: int.to_bytes(length, byteorder, \*, signed=False)

		Return an array of bytes representing an integer.
Expand Down

3 changes: 3 additions & 0 deletions 3 Doc/whatsnew/3.10.rst

Show comments

View file

Open in desktop

Original file line number	Diff line number	Diff line change
Expand Up		@@ -70,6 +70,9 @@ Summary -- Release highlights
		New Features
		============

		* The :class:`int` type has a new method :meth:`int.bit_count`, returning the
		number of ones in the binary expansion of a given integer, also known
		as the population count. (Contributed by Niklas Fiekas in :issue:`29882`.)


		Other Language Changes
Expand Down

3 changes: 2 additions & 1 deletion 3 Lib/test/test_doctest.py

Show comments

View file

Open in desktop

Original file line number	Diff line number	Diff line change
Expand Up		@@ -669,7 +669,7 @@ def non_Python_modules(): r"""
		True
		>>> real_tests = [t for t in tests if len(t.examples) > 0]
		>>> len(real_tests) # objects that actually have doctests
		13
		14
		>>> for t in real_tests:
		... print('{} {}'.format(len(t.examples), t.name))
		...
Expand All		@@ -682,6 +682,7 @@ def non_Python_modules(): r"""
		1 builtins.hex
		1 builtins.int
		3 builtins.int.as_integer_ratio
		2 builtins.int.bit_count
		2 builtins.int.bit_length
		5 builtins.memoryview.hex
		1 builtins.oct
Expand Down

11 changes: 11 additions & 0 deletions 11 Lib/test/test_long.py

Show comments

View file

Open in desktop

Original file line number	Diff line number	Diff line change
Expand Up		@@ -1016,6 +1016,17 @@ def test_bit_length(self):
		self.assertEqual((a+1).bit_length(), i+1)
		self.assertEqual((-a-1).bit_length(), i+1)

		def test_bit_count(self):
		for a in range(-1000, 1000):
		self.assertEqual(a.bit_count(), bin(a).count("1"))

		for exp in [10, 17, 63, 64, 65, 1009, 70234, 1234567]:
		a = 2**exp
		self.assertEqual(a.bit_count(), 1)
		self.assertEqual((a - 1).bit_count(), exp)
		self.assertEqual((a ^ 63).bit_count(), 7)
		self.assertEqual(((a - 1) ^ 510).bit_count(), exp - 8)

		def test_round(self):
		# check round-half-even algorithm. For round to nearest ten;
		# rounding map is invariant under adding multiples of 20
Expand Down

2 changes: 2 additions & 0 deletions 2 Misc/NEWS.d/next/Core and Builtins/2019-06-02-11-29-15.bpo-29882.AkRzjb.rst

Show comments

View file

Open in desktop

Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,2 @@
		Add :meth:`int.bit_count()`, counting the number of ones in the binary
		representation of an integer. Patch by Niklas Fiekas.

27 changes: 26 additions & 1 deletion 27 Objects/clinic/longobject.c.h

Show comments

View file

Open in desktop

Some generated files are not rendered by default. Learn more about how customized files appear on GitHub.

Oops, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

70 changes: 70 additions & 0 deletions 70 Objects/longobject.c

Show comments

View file

Open in desktop

Original file line number	Diff line number	Diff line change
Expand Up		@@ -5304,6 +5304,75 @@ int_bit_length_impl(PyObject *self)
		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]/
		{
Comment thread mdickinson marked this conversation as resolved. Resolved Uh oh! There was an error while loading. Please reload this page.
		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. */
Comment thread vstinner May 27, 2020 Copy link Copy Markdown Member There was a problem hiding this comment. Choose a reason for hiding this comment The reason will be displayed to describe this comment to others. Learn more. Nice comment, thanks! Before the comment, I was surprised by the two loops. Sorry, something went wrong. Uh oh! There was an error while loading. Please reload this page. All reactions
		Py_ssize_t ndigits_fast = Py_MIN(ndigits, PY_SSIZE_T_MAX/PyLong_SHIFT);
Comment thread vstinner May 27, 2020 Copy link Copy Markdown Member There was a problem hiding this comment. Choose a reason for hiding this comment The reason will be displayed to describe this comment to others. Learn more. I proposed to work use size_t for bit_count, but then I realzied that i is a Py_ssize_t, so it's better to leave the code as it is: work on Py_ssize_t for i and bit_count. Sorry, something went wrong. Uh oh! There was an error while loading. Please reload this page. All reactions
		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;
Comment thread niklasf marked this conversation as resolved. Resolved Uh oh! There was an error while loading. Please reload this page.
		}

		/* 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
Expand Down Expand Up		@@ -5460,6 +5529,7 @@ static PyMethodDef long_methods[] = {
		{"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
Expand Down

Add this suggestion to a batch that can be applied as a single commit. This suggestion is invalid because no changes were made to the code. Suggestions cannot be applied while the pull request is closed. Suggestions cannot be applied while viewing a subset of changes. Only one suggestion per line can be applied in a batch. Add this suggestion to a batch that can be applied as a single commit. Applying suggestions on deleted lines is not supported. You must change the existing code in this line in order to create a valid suggestion. Outdated suggestions cannot be applied. This suggestion has been applied or marked resolved. Suggestions cannot be applied from pending reviews. Suggestions cannot be applied on multi-line comments. Suggestions cannot be applied while the pull request is queued to merge. Suggestion cannot be applied right now. Please check back later.

You are visitor 01402520 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.

GeezerVison

bpo-29882: Add an efficient popcount method for integers #771

Uh oh!

bpo-29882: Add an efficient popcount method for integers #771

Uh oh!

Uh oh!

Diff view

Diff view

There are no files selected for viewing

Uh oh!

Uh oh!

Uh oh!

vstinner May 27, 2020

Choose a reason for hiding this comment

Uh oh!

vstinner May 27, 2020

Choose a reason for hiding this comment

Uh oh!

Uh oh!