Brute-force superoptimization finds branchless 4-op formula for lowest float bit

A formula found by search, not by hand

A developer building a floating-point library has swapped a hand-written routine for a branchless four-operation formula that no human managed to derive — because it was discovered by an exhaustive computer search. According to a post on purplesyringa.moe that surfaced on the Hacker News front page, the brute-force enumeration ran in roughly four minutes and produced a rewrite that conventional compilers would never attempt.

The problem

The routine takes a float f and returns the float corresponding to the lowest set bit in f. Straightforward bit twiddling handles most inputs, but the obvious algorithm breaks for powers of two, so the author's original Rust implementation needed a conditional branch to special-case them. As the post explains, that branch was unwelcome on two counts: it penalized the common case, and branches can be mispredicted. Attempts to find a uniform formula by hand went nowhere.

Enumerating every candidate formula

Instead of continuing to guess — or delegating to a language model, which the author argues can overlook possibilities or lean toward well-known patterns — the approach was to enumerate every expression up to a fixed operation count. Because a six-operation solution already existed, only formulas of five operations or fewer needed checking. The candidate operation set was deliberately small: integer addition and subtraction, bitwise AND, OR and XOR, and a floating-point subtraction in final position, with comparisons considered as a possibility.

Per the post, the combinatorics stay manageable: 7,776 ways to choose the operations and 42 possible parenthesis placements. The inputs to each operation are either the variable x or a constant, and rather than allow arbitrary constants, the author curated a pool of 64 values aligned with the fields of the float's binary representation — sign, exponent and mantissa boundaries. That culling is what keeps the input-assignment space tractable, since many remaining combinations can still be pruned during the search.

How the search prunes

The expression set is built up inductively: formulas with n operations are assembled from all pairs of formulas with k and n−1−k operations. Duplicates are eliminated by comparing each candidate's outputs across the test cases — 20 by the end of the process, costing 80 bytes of storage per expression. This behavioral deduplication matters because syntactically different expressions such as adding two constants in either order produce identical values; keeping just one representative makes later iterations dramatically cheaper, which is why the whole search finishes in minutes. Deduplication is skipped on the final round to save time and memory.

Correctness is checked against representative test cases rather than a theorem prover, which the author judged too slow. If a candidate turns out to have a counterexample, it is simply added to the test set and the search is repeated.

The result

The search turned up several valid five-operation formulas but nothing with four — under its own model. That model has a blind spot: it counts every use of a subexpression as a separate operation and cannot exploit reuse. After manually inspecting every candidate, the very last one admitted a shared intermediate, collapsing it to four operations.

The winning trick: compute a, which is x with its mantissa bits cleared, and then use a minus x's raw bits. That subtraction is equivalent to the negation of x's mantissa bits, so it folds a negation into an existing operation and saves one step — a rewrite the author describes as genuinely surprising to discover by machine. The formula does behave slightly differently for powers of two, flipping the sign bit, a deviation the author considers acceptable. The code now lives in a work-in-progress FPU emulator.

Why it matters

Superoptimization — using a compiler-style search to find optimal instruction sequences for loop-free code, per the Wikipedia definition the post cites — performs reasoning that mainstream optimizers don't: they excel at mechanical transformations but rarely invent a novel approach to a problem. This walkthrough shows the technique is practical at small scale. Bound the operation count, curate the constant pool, deduplicate by observed behavior, and refine with counterexamples, and an ordinary machine returns an answer in minutes. It also exposes a real limitation: expression enumeration without common-subexpression awareness can miss the true optimum, and here a short manual review of machine-proposed candidates was the corrective. For performance-critical numeric code, exhaustive search over a small design space remains a credible alternative to both human cleverness and generative models.