Superoptimizing an FPU Emulator

This describes designing a branchless routine to return the lowest set bit of a 32-bit float by searching for a compact algebraic formula instead of using an if to handle powers of two. A straightforward bit-twiddling approach required a branch that hurt performance, so a brute-force superoptimization was attempted: enumerate expressions up to five operations built from integer add/sub and bitwise AND/OR/XOR, some constants targeting float bitfields, and a final floating-point subtraction. The search constructs expressions inductively, deduplicates by output vectors across about twenty test cases to prune equivalent formulas, and limits constants to a small useful set; this allows the huge combinatorial space to be explored in minutes while keeping memory manageable.

The exhaustive search produced several five-op candidates and, after manual inspection for reusable subexpressions, one collapsed effectively to four operations by computing a = x_bits & !MANTISSA and reusing it. The working sequence computes a and a blended bitmask from a − x_bits (which algebraically equals the negated mantissa portion), converts appropriate bitmasks back to floats, and subtracts to yield the lowest set bit. It behaves slightly differently for exact powers of two (flipping the sign bit) but is acceptable for the intended emulator. The result demonstrates that brute-force formula enumeration can uncover clever algebraic rewrites that human design missed.