Multiplying our way out of division — Matt Godbolt’s blog
A very silly optimisation for the “binary to decimal” conversion problem:
The compiler has turned division by a constant ten into a multiply and a shift. There’s a magic constant 0xcccccccd and a shift right of 35! Shifting right by 35 is the same as dividing by 235 - what’s going on? [..]
What’s happening is that 0xcccccccd / 2**35 is very close to ? (around 0.10000000000582077). By multiplying our input value by this constant first, then shifting right, we’re doing fixed-point multiplication by ? - which is division by ten. The compiler knows that for all possible unsigned integer values, this trick wil…
Multiplying our way out of division — Matt Godbolt’s blog
A very silly optimisation for the “binary to decimal” conversion problem:
The compiler has turned division by a constant ten into a multiply and a shift. There’s a magic constant 0xcccccccd and a shift right of 35! Shifting right by 35 is the same as dividing by 235 - what’s going on? [..]
What’s happening is that 0xcccccccd / 2**35 is very close to ? (around 0.10000000000582077). By multiplying our input value by this constant first, then shifting right, we’re doing fixed-point multiplication by ? - which is division by ten. The compiler knows that for all possible unsigned integer values, this trick will always give the right answer.
Tags: hacks optimization bit-hacking binary decimal fixed-point arithmetric tricks