Kernighan's bit count in Python
Repeatedly clears the lowest set bit with x &= x-1, so it runs in time proportional to the number of 1-bits.
- File
kernighan_popcount.py, 19 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/kernighan-popcount/. The authors are listed in prov/TVK2SZ.jsonl.
def kernighan_popcount(x: int) -> int:
"""Return the number of 1-bits of the non-negative integer x.
Each iteration clears the lowest 1-bit with x & (x - 1), so the loop runs
exactly popcount(x) times. A negative x has infinitely many 1-bits in
Python's two's complement view, so it is rejected; mask it to w bits first.
Cost: popcount(x) iterations, each O(1) word operations for x < 2**w.
"""
if x < 0:
raise ValueError("x must be non-negative; mask it to a word size first")
c = 0 # @line L1
while x != 0: # @line L2
x &= x - 1 # @line L3
c += 1 # @line L4
return c # @line L5
test_kernighan_popcount.py 37 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/kernighan-popcount/. The authors are listed in prov/TVK2SZ.jsonl.
import random
import pytest
from kernighan_popcount import kernighan_popcount
def test_example() -> None:
assert kernighan_popcount(180) == 4
def test_edges() -> None:
assert kernighan_popcount(0) == 0
assert kernighan_popcount(1) == 1
assert kernighan_popcount(2**64 - 1) == 64
assert kernighan_popcount(2**63) == 1
assert kernighan_popcount((-1) & 0xFFFFFFFF) == 32
def test_negative_rejected() -> None:
with pytest.raises(ValueError):
kernighan_popcount(-1)
def test_all_16_bit_words() -> None:
for x in range(1 << 16):
assert kernighan_popcount(x) == bin(x).count("1")
def test_random_64_bit() -> None:
rng = random.Random(136)
for _ in range(5000):
x = rng.getrandbits(64)
assert kernighan_popcount(x) == bin(x).count("1")
What the next level needs
- the tests did not run in this build