Gosper's hack in Python
Compute the next integer with the same number of set bits in a few arithmetic operations.
- File
gospers_hack.py, 39 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/gospers-hack/. The authors are listed in prov/EEBZ0F.jsonl.
from collections.abc import Iterator
def gospers_hack(x: int, w: int = 64) -> int:
"""Return the next larger w-bit word with the same number of 1-bits as x.
Precondition: 0 < x < 2**w. The arithmetic wraps modulo 2**w, as on a
machine. If x is the largest w-bit word with its number of ones, the
result wraps and is smaller than x, so the caller must stop first.
Cost: O(1) word operations.
"""
if not 0 < x < (1 << w):
raise ValueError("x must satisfy 0 < x < 2**w")
mask = (1 << w) - 1
smallest = x & (-x & mask) # @line L1
ripple = (x + smallest) & mask # @line L2
ones = x ^ ripple # @line L3
ones = (ones >> 2) // smallest # @line L4
return ripple | ones # @line L5
def k_subsets(n: int, k: int) -> Iterator[int]:
"""Yield the masks of all k-subsets of {0, ..., n-1} in increasing order.
Uses Python integers, so there is no word-size limit. Cost: O(1) word
operations for each mask, C(n, k) masks in all.
"""
if k < 0 or k > n:
return
if k == 0:
yield 0
return
x = (1 << k) - 1
while x < (1 << n):
yield x
x = gospers_hack(x, n + 1)
test_gospers_hack.py 80 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/gospers-hack/. The authors are listed in prov/EEBZ0F.jsonl.
import itertools
import math
import random
import pytest
from gospers_hack import gospers_hack, k_subsets
def popcount(v: int) -> int:
return bin(v).count("1")
def brute_next(x: int, w: int) -> int | None:
k = popcount(x)
for y in range(x + 1, 1 << w):
if popcount(y) == k:
return y
return None
def test_example() -> None:
assert gospers_hack(92, 8) == 99
assert list(k_subsets(5, 3)) == [7, 11, 13, 14, 19, 21, 22, 25, 26, 28]
assert gospers_hack(28, 8) == 35
def test_exhaustive_small_words() -> None:
for w in range(1, 13):
for x in range(1, 1 << w):
want = brute_next(x, w)
got = gospers_hack(x, w)
if want is not None:
assert got == want
else:
k = popcount(x)
assert got < x
assert popcount(got) == max(k - 2, 0)
def test_last_combination_wraps() -> None:
assert gospers_hack(0b11100000, 8) == 1
assert gospers_hack(0b10000000, 8) == 0
def test_zero_is_rejected() -> None:
with pytest.raises(ValueError):
gospers_hack(0, 8)
def test_k_subsets_match_itertools() -> None:
for n in range(0, 11):
for k in range(0, n + 1):
want = sorted(sum(1 << i for i in c) for c in itertools.combinations(range(n), k))
got = list(k_subsets(n, k))
assert got == want
assert len(got) == math.comb(n, k)
def scan_next(x: int) -> int:
"""Independent oracle: scan for the lowest 1 with a 0 above it."""
i = 0
below = 0
while not ((x >> i) & 1 and not (x >> (i + 1)) & 1):
below += (x >> i) & 1
i += 1
high = (x >> (i + 2)) << (i + 2)
return high | (1 << (i + 1)) | ((1 << below) - 1)
def test_random_64_bit_against_scan() -> None:
rng = random.Random(175)
for _ in range(3000):
x = rng.randrange(1, 1 << 64)
if (x + (x & -x)) >> 64:
continue # the last combination of its size: no answer in 64 bits
assert gospers_hack(x, 64) == scan_next(x)
What the next level needs
- the tests did not run in this build