Beating the compiler at signed 32-bit division

Daniel Lemire shows that compilers leave a bit unused when dividing signed 32-bit integers by constants on 64-bit CPUs. A 33-bit multiplier fits in a signed 64-bit product, so the correction step can be dropped, which affects about 38% of divisors from 3 to 1000. In his benchmarks, latency falls from 10 to 8 cycles on Intel, and clang throughput improves over 20%. His fastmod 0.2.0 removes a sign branch, running 4x faster than 0.1.0 on Intel. These are single-author measurements on one Intel and one Apple chip.