19 Feb 2026

Magic Numbers: Why Your C++ Compiler Refuses to Divide

C++
System Engineering

Addition and multiplication at hardware level is very straightforward and simple. It's just addition and shifting of bits. But division is different. It's a long iterative process. To divide A by B, the CPU has to guess, subtract, shift, and repeat, much like the "long division" you did in third grade. 🤪

For reference, if a MULTIPLY (MUL) operation takes 3 cycles, a DIVISION (DIV) operation might take up to 80 cycles. That's a big difference. In a high-frequency trading app or a physics engine, that 30× slowdown is insanely slow at scale.

Note: this algorithm only works for integer division. It will not give decimal values. Cycle counts are illustrative and depend on the processor and operands.

The magic number

So how do compilers optimize this at a low level? Since we can't make the division any faster (for now), we use a loophole. In mathematics:

x / d = x × (1 / d)

So instead of dividing by a constant d, we can instead multiply it with a constant 1/d. But computers struggle with the decimals in 1/d. The solution? Fixed-point reciprocals.

We take 1/d, scale it up by a massive power of two (2^k) until it's a huge integer, and then multiply by that. Later, we "undo" the scaling by shifting the bits back.

C++ division by three compiled into assembly using a magic multiplier and a right shift — Division by three, as seen by the compiler.

The visual process

Let's look at the assembly code again. To divide by 3, the compiler uses the big ahh magic number, hex coded as 0xAAAAAAAAAAAAAAAB (which is roughly 2^65 / 3). This example uses an unsigned 64-bit integer.

Multiply: You multiply your 64-bit number by the 64-bit magic number. This creates a 128-bit result.
The high-half trick: The mul instruction puts the top 64 bits in rdx. By just looking at rdx, you have automatically divided the result by 2^64 (shifted right by 64 bits).
The final tweak: A quick shr (shift right) finishes the job, dividing by the remaining 2^1 to reach the total 2^65 scale.

And we just divided any number by 3 using only a multiply and a shift. Total time? Around 4 cycles in this illustrative comparison. You just saved 70+ cycles of CPU time.

How is the number calculated?

GCC doesn't guess. It uses an algorithm called Granlund–Montgomery. Here is the algorithm the compiler follows when it sees x / d, at a high level:

Find the scale (k): It finds a power of 2 (2^k) that is larger than the maximum possible value of x.
Calculate the multiplier (m): It calculates m = ceil((2^k) / d).
Verify integrity: It runs a check to ensure that for every possible value of x (from 0 to 2^64 - 1), the rounding error of the multiplication doesn't change the integer result. It uses number theory to verify this step, not an iterative process for each number.
Emit assembly: If the divisor is even, it might divide by a power of 2 first (using a shift) and then apply the magic number for the remaining odd factor.

Final end-to-end flow

When you hit "Compile," this is how the division looks:

Step 1: Check for a constant divisor. GCC checks: "Is the divisor a constant?" (e.g. x / 7). If it's a variable (x / y) that the compiler cannot determine ahead of time, this constant-multiplier technique doesn't apply and it generally uses division.
Step 2: Strength reduction. The compiler decides if a simple shift works (for unsigned division by 2, 4, 8…).
Step 3: The magic calculation. It runs the math above to find the smallest multiplier and the most efficient shift. Some divisors need an additional correction step.
Step 4: Instruction selection. For our divide-by-three example, it writes the assembly: movabs (load magic), mul (multiply), shr (shift).

And that's how logically simple integer division is for compilers.

If you liked this explanation, would you like me to explain how decimal division takes place (FPU)? Let me know on X.