de Bruijn bit scan in Python
Isolates the lowest set bit, multiplies by a de Bruijn constant and indexes a table to get the bit position in constant time.
- File
de_bruijn_bit_scan.py, 52 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/de-bruijn-bit-scan/. The authors are listed in prov/3BENJ1.jsonl.
# For each word size w = 2^n: the de Bruijn constant D (a binary de Bruijn
# sequence of order n whose top n bits are zero) and n.
_CONSTANTS: dict[int, tuple[int, int]] = {
8: (0x1D, 3),
16: (0x09AF, 4),
32: (0x077CB531, 5),
64: (0x03F79D71B4CB0A89, 6),
}
def build_table(d: int, w: int, n: int) -> tuple[int, ...]:
"""Return T with T[((2^k * d) mod 2^w) >> (w - n)] = k for 0 <= k < w.
Raises ValueError if two values of k give the same index, that is, if d
is not a valid multiplier for this word size. Cost: Theta(w).
"""
mask = (1 << w) - 1
table = [-1] * w
for k in range(w):
i = (((1 << k) * d) & mask) >> (w - n)
if table[i] != -1:
raise ValueError("d is not a de Bruijn multiplier for this w")
table[i] = k
return tuple(table)
_TABLES: dict[int, tuple[int, ...]] = {
w: build_table(d, w, n) for w, (d, n) in _CONSTANTS.items()
}
def de_bruijn_bit_scan(x: int, w: int = 64) -> int:
"""Return the index of the lowest 1-bit of x (the trailing-zero count).
Precondition: w is 8, 16, 32 or 64, and x is an unsigned w-bit word with
x != 0. Raises ValueError otherwise. Cost: one negation, one AND, one
multiplication, one shift and one table read, so O(1) word operations.
"""
if w not in _CONSTANTS:
raise ValueError("w must be 8, 16, 32 or 64")
if not 0 < x < (1 << w):
raise ValueError("x must satisfy 0 < x < 2^w")
d, n = _CONSTANTS[w]
table = _TABLES[w]
mask = (1 << w) - 1
b = x & (-x & mask) # @line L1
p = (b * d) & mask # @line L2
i = p >> (w - n) # @line L3
return table[i] # @line L4
test_de_bruijn_bit_scan.py 59 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/de-bruijn-bit-scan/. The authors are listed in prov/3BENJ1.jsonl.
import random
import pytest
from de_bruijn_bit_scan import build_table, de_bruijn_bit_scan
def oracle(x: int) -> int:
return (x & -x).bit_length() - 1
def test_page_examples() -> None:
assert de_bruijn_bit_scan(104, 8) == 3
assert de_bruijn_bit_scan(180, 8) == 2
assert de_bruijn_bit_scan(0x00F00000, 32) == 20
def test_tables_on_page() -> None:
assert build_table(0x1D, 8, 3) == (0, 1, 6, 2, 7, 5, 4, 3)
assert build_table(0x077CB531, 32, 5)[:8] == (0, 1, 28, 2, 29, 14, 24, 3)
def test_all_8_and_16_bit_words() -> None:
for x in range(1, 1 << 8):
assert de_bruijn_bit_scan(x, 8) == oracle(x)
for x in range(1, 1 << 16):
assert de_bruijn_bit_scan(x, 16) == oracle(x)
def test_every_single_bit() -> None:
for w in (8, 16, 32, 64):
for k in range(w):
assert de_bruijn_bit_scan(1 << k, w) == k
assert de_bruijn_bit_scan((1 << w) - (1 << k), w) == k
def test_bad_input() -> None:
with pytest.raises(ValueError):
de_bruijn_bit_scan(0, 32)
with pytest.raises(ValueError):
de_bruijn_bit_scan(1 << 32, 32)
with pytest.raises(ValueError):
de_bruijn_bit_scan(5, 12)
with pytest.raises(ValueError):
build_table(0x1F, 8, 3)
def test_random_64_bit() -> None:
rng = random.Random(1998)
for _ in range(5000):
x = rng.randrange(1, 1 << 64) >> rng.randrange(64)
x = max(x, 1)
assert de_bruijn_bit_scan(x, 64) == oracle(x)
y = x & 0xFFFFFFFF
if y:
assert de_bruijn_bit_scan(y, 32) == oracle(y)
What the next level needs
- the tests did not run in this build