I noticed something strange in the assembly generated when compiling a program
using gcc an optimization turned off. Here it is in Figure 1
(though using optimization level 3 just to simplify, but it still shows in level 0).
In this generated assembly, we see instead of using the div operator,
something strange is going on with the number 1717986919 and shifting. My first
attempts at searching for this phenomenon online were not helpful. The first result
for the number was on Amazon as a book identifier. This number also shows up on
stack overflow, however it is no more helpful. No one on the post is talking about
why this number is in the generated code (or perhaps they all know this arcane
secret and don’t wish share). Eventually, I found out what was going on. Even
with no optimization, the compiler prefers to generate multiplication operator
over the division operator.
We will consider unsigned integer division first. Let
d
be some constant divisor, and n
our numerator (for now let’s make n
a multiple of d). We will assume
integers are 32 bits. In order to computer
n/d,
first we need to know the values l
and i where
d = l2i.
So to begin out division, we can shift n
by i bits. Now we must divide this result
be l. Since
l will be odd, there exists some
inverse of l, called
j where
lj = 1(mod 232)
So for any number x,
x/l = (xj)/(lj)=xj.
So now all that is left after the shift is to multiply by
j, and we will
have computed n/d.
Dealing with remainder can go pretty in depth, and I recommend reading the chapter in Hacker’s Delight about this topic [1]. Another write up can be found in the MSDN blog archive [2].
int div20(int n){
return a/20;
}
.cfi_startproc
movl %edi, %eax
movl $1717986919, %edx
sarl $31, %edi
imull %edx
sarl $3, %edx
movl %edx, %eax
subl %edi, %eax
ret
.cfi_endproc
1 Hacker’s Delight Chapter 10. ( http://www.hackersdelight.org/divcMore.pdf )
2 MSDN Blog Archive ( https://blogs.msdn.microsoft.com/devdev/2005/12/12/integer-division-by-constants/ )