CHAPTER 41. DIVISION BY 9 CHAPTER 41. DIVISION BY 9

Chapter 41

Division by 9

A very simple function:

int f(int a)
{
return a/9;
};

41.1 x86

...is compiled in a very predictable way:

Listing 41.1: MSVC

_a$ = 8 ; size = 4
_f PROC
push ebp
mov ebp, esp
mov eax, DWORD PTR _a$[ebp]
cdq ; sign extend EAX to EDX:EAX
mov ecx, 9
idiv ecx
pop ebp
ret 0
_f ENDP

IDIVdivides the 64-bit number stored in theEDX:EAXregister pair by the value in theECX. As a result,EAXwill contain
thequotient, andEDX—the remainder. The result is returned from thef()function in theEAXregister, so the value is not
moved after the division operation, it is in right place already. SinceIDIVuses the value in theEDX:EAXregister pair, the
CDQinstruction (beforeIDIV) extends the value inEAXto a 64-bit value taking its sign into account, just asMOVSXdoes.
If we turn optimization on (/Ox), we get:

Listing 41.2: Optimizing MSVC

_a$ = 8 ; size = 4
_f PROC

mov ecx, DWORD PTR _a$[esp-4]
mov eax, 954437177 ; 38e38e39H
imul ecx
sar edx, 1
mov eax, edx
shr eax, 31 ; 0000001fH
add eax, edx
ret 0
_f ENDP

This is division by multiplication. Multiplication operations work much faster. And it is possible to use this trick^1 to produce
code which is effectively equivalent and faster.

(^1) Read more about division by multiplication in [War02, pp. 10-3]