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>

1 files changed, 11 insertions, 0 deletions

diff --git a/Lib/test/test_long.py b/Lib/test/test_long.py
index 7ce37e8..c97842b 100644
--- a/Lib/test/test_long.py
+++ b/Lib/test/test_long.py
@@ -1016,6 +1016,17 @@ class LongTest(unittest.TestCase):
             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