A developer building a floating-point library used exhaustive search to replace a slow conditional with a short formula that works for every input, including powers of two.
The task was a function that takes a float and returns the value of its lowest set bit. A direct bit-twiddling approach fails for powers of two, so the author added an if statement. That branch slowed the common case and could be mispredicted, and manual attempts to remove it went nowhere.
Instead of asking an AI model, the author tried superoptimization: brute-forcing every possible formula up to a given number of operations. Correctness was checked against a set of representative test cases, with any counterexample added to the list before repeating. The search was built up inductively, combining smaller expressions into larger ones. Expressions that produced identical outputs were pruned, which kept the run time to a matter of minutes. Constants were limited to values covering the different fields of the float format.
The search found several formulas that were shorter than the original, but none at the target size. However, the method counts a repeated subexpression twice, so it misses chances for reuse. After checking the candidates by hand, the author found that the last one could reuse a value and fit the smaller target. It works by rewriting one masked term as a subtraction and merging it with a negation, saving an operation. For powers of two it flips the sign bit, which the author does not need.
The resulting code now lives in the author's work-in-progress FPU emulator.
Source: Lobster
