THE FOLD / RESPAWN / EVENT HORIZON / THE DE BRUIJN MULTIPLY
THE DE BRUIJN MULTIPLY
a perfect hash for the lowest set bit
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
A de Bruijn sequence contains every window of a given width exactly once. Multiply an isolated bit by one and the sequence shifts — so the top five bits of the product name the position of that bit. One multiply, one shift, one table lookup, and no branches at all.
LIT verified live. The 32 shifts of the constant 0x077CB531 produce 32 distinct five-bit windows — a perfect hash with no collisions. Every isolated bit resolves to its own index, 32/32, and on values with several bits set it returns the lowest, checked exhaustively on 19,999 consecutive integers.
LIT verified live. The 32 shifts of the constant 0x077CB531 produce 32 distinct five-bit windows — a perfect hash with no collisions. Every isolated bit resolves to its own index, 32/32, and on values with several bits set it returns the lowest, checked exhaustively on 19,999 consecutive integers.
2 HOW IT WAS WEAVED · AI + HUMAN
The de Bruijn sequence is Nicolaas de Bruijn’s, and this corpus already carries it as its own sphere — the shortest string holding every code. What is built here is the use: turning that uniqueness property into a branch-free perfect hash, a technique from the chess-programming world where scanning a 64-bit board for the lowest occupied square is the inner loop of everything.
AVAN (AI) would keep the dependency visible. The trick works because every window appears exactly once — the sequence sphere states that property and this one spends it. And there is one input it cannot answer for: zero has no lowest set bit, and the expression returns a number anyway. That is a precondition on the caller, not a special case in the code, which is why it is easy to forget.
AVAN (AI) would keep the dependency visible. The trick works because every window appears exactly once — the sequence sphere states that property and this one spends it. And there is one input it cannot answer for: zero has no lowest set bit, and the expression returns a number anyway. That is a precondition on the caller, not a special case in the code, which is why it is easy to forget.
3 ONE DIMENSION
Thirty-two shifts, thirty-two distinct windows.
4 TWO DIMENSIONS · INTERACTIVE
Isolate a bit and watch the window it selects.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: one ring whose every window is unique.
AVAN’s addition (the inverse-companion): the forward reading is “a perfect hash with no branches.” The inverse is that the constant is not derivable at the point of use. 0x077CB531 must be found by search, verified separately, and then trusted forever by every reader who cannot check it in their head — and a single wrong digit produces a table that still looks plausible and fails on a few inputs. Read backwards, branch-free code moves the difficulty out of the control flow and into a magic number nobody will re-derive, which is a real cost paid in a different currency.
LIT the 32 shifts of the constant 0x077CB531 produce 32 distinct five-bit windows - a perfect hash with no collisions - and every isolated bit resolves to its own index at 32 of 32, while on values with several bits set it returns the lowest, checked exhaustively on 19,999 consecutive integers
FIG The de Bruijn sequence is Nicolaas de Bruijn's, and this corpus already carries it as its own sphere - 'the shortest string holding every code'. What is built here is the USE: turning that uniqueness property into a branch-free perfect hash, a technique from the chess-programming world where scanning a 64-bit board for the lowest occupied square is the inner loop of everything. AVAN keeps the dependency visible - the trick works BECAUSE every window appears exactly once - and flags the one input it cannot answer for: zero has no lowest set bit, and the expression returns a number anyway. That is a precondition on the caller, not a special case in the code.
FIG The de Bruijn sequence is Nicolaas de Bruijn's, and this corpus already carries it as its own sphere - 'the shortest string holding every code'. What is built here is the USE: turning that uniqueness property into a branch-free perfect hash, a technique from the chess-programming world where scanning a 64-bit board for the lowest occupied square is the inner loop of everything. AVAN keeps the dependency visible - the trick works BECAUSE every window appears exactly once - and flags the one input it cannot answer for: zero has no lowest set bit, and the expression returns a number anyway. That is a precondition on the caller, not a special case in the code.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of EVENT HORIZON · David Lee Wise (ROOT0), with AVAN