Why does GCC turn division by a constant into a multiply by a strange magic number?

It is fixed-point multiplication by the reciprocal. Dividing by 10 is multiplying by 1/10, and 1/10 scaled by 2^35 is 3435973836.8; rounded up that is 3435973837, or 0xCCCCCCCD. The code computes (x × 0xCCCCCCCD) >> 35. Take x = 1234: the product is 4,239,991,714,858, and dividing by 2^35 (34,359,738,368) gives 123.4000000072, which truncates to 123.

Because the constant is rounded up, the result is always slightly too large, never too small. The excess is x × 0.2 / 2^35, which stays below 0.025 for any x under 2^32. The fractional part of x/10 is at most 0.9, so the excess can never push the value across the next integer, and truncation gives the exact quotient for every 32-bit input.

The reason is cost. Hardware division is the slowest common integer operation: a multiply has a latency of about three cycles on current x86 cores and a shift one, while a 32-bit DIV takes several times longer, tens of cycles on many older cores. The exact figures depend on the microarchitecture, but the multiply and shift always win.

The remainder uses the same quotient: x % 10 is computed as x - (x / 10) * 10. For powers of two an unsigned division is just a shift, so x / 8 becomes shr eax, 3. A signed division by 8 needs a small correction, adding 7 to negative inputs before the arithmetic shift, because C rounds towards zero while a shift rounds towards minus infinity: -9 / 8 must be -1, but -9 >> 3 is -2.

Not every divisor is as tidy as 10. For some, 7 being the classic, the exact constant needs 33 bits, so the compiler emits a longer sequence: multiply by the low 32 bits of the constant, then a subtract, a shift and an add to account for the missing top bit. Signed division uses a signed high multiply and then adds one when the dividend is negative, so that the quotient rounds towards zero.

The method comes from the paper "Division by Invariant Integers using Multiplication" by Granlund and Montgomery, and the book Hacker's Delight has a full chapter with code for deriving the constants. If a divisor is only known at run time but is reused many times, you can apply the same idea yourself by computing the constant once before the loop.

On microcontrollers it matters even more. Cortex-M0/M0+ and 8-bit AVR have no divide instruction, so x / y with a variable divisor calls a library routine (__aeabi_uidiv in the ARM run-time ABI) that works through the bits in a loop. Cortex-M3 and M4 do have UDIV and SDIV, which take roughly 2 to 12 cycles, and UMULL, which returns the full 64-bit product of two 32-bit values, so there the compiler is free to use either method for a constant divisor.

Practical advice for small cores: prefer power-of-two divisors for buffer sizes and averaging lengths, use unsigned types so that the division becomes a single shift, and keep divisions out of interrupt handlers. To check, disassemble with arm-none-eabi-objdump -d and look for bl __aeabi_uidiv.