Division

Written by me, proof-read by an LLM.
Details at end.

Broadly computers have the same kind of trouble with integer arithmetic that we do, addition and subtraction are quick, multiplication takes a bit longer, and then division is where things start to get really slow. On an average x86, addition is single-cycle (and many can happen at once), multiplication is three or so cycles, and then division can be up to a hundred!¹ And usually only a single divide can happen at a time, too.

It’s worth avoiding divides then, and compilers know this too. Let’s start with the easy cases: you probably know that shifting right effectively divides by powers of two. You’ve likely seen return x >> 9; to divide the int x by 512, right? Let’s see what the compiler does if we use the more obvious return x / 512;:

Well, the stupid compiler has generated all these extra instructions! How dumb! Clearly we can’t trust compilers and should go back to our much cooler x >> 9, right?

No… the compiler is being correct here. This is a great example of the compiler doing what you asked not what you meant. When you divide in C, the language rules are “round towards zero”. That’s great, shifting down does indeed round down. But only for positive numbers. Shifting (effectively) rounds towards negative infinity. The compiler is forced to emit those extra instructions to appropriately round negative numbers up! We may not have realised it, but by using the signed integer type int, we asked the compiler to do this.

test edi, edi         ; set sign flags etc based on x
lea eax, [rdi+511]    ; eax = x + 511 (bias for negative rounding)
cmovns eax, edi       ; eax = (x >= 0) ? x : (x + 511)
sar eax, 9            ; eax = eax >> 9

It’s a neat sequence that does what we asked. But what if we knew x was never negative? Can we get the compiler to do what we wanted? Absolutely:

Simply by dividing by an unsigned constant 512, we tell the compiler what we wanted, and it does the right thing².

This idea will pop up again in later episodes: sometimes we have to be very careful to align what we’d like to happen with what we actually wrote in our code. The compiler has its hands tied by the language specification, and sometimes it does things that may surprise you if you don’t remember that. Tools like Compiler Explorer can help you develop your intuition.

See the video that accompanies this post.

This post is day 6 of Advent of Compiler Optimisations 2025, a 25-day series exploring how compilers transform our code.

This post was written by a human (Matt Godbolt) and reviewed and proof-read by LLMs and humans.

Support Compiler Explorer on Patreon or GitHub, or by buying CE products in the Compiler Explorer Shop.