162 Integer Optimizations Chapter 8
25112 Rev. 3.06 September 2005
Software Optimization Guide for AMD64 Processors
Simpler Code for Restricted Dividend
Integer division by a constant can be made faster if the range of the dividend is limited, which
removes a shift associated with most divisors. For example, for a divide by 10 operation, use the
following code if the dividend is less than 4000_0005h:
mov eax, dividend
mov edx, 01999999Ah
mul edx
mov quotient, edx
Signed Division by Multiplication of ConstantAlgorithm: Divisors 2 <= d < 231
These algorithms work if the divisor is positive. If the divisor is negative, use abs(d) instead of d, and
append a neg edx instruction to the code. These changes make use of the fact that n/–d=–(n/d).
; a = algorithm
; m = multiplier
; s = shift count
; a == 0
mov eax, m
imul dividend
mov eax, dividend
shr eax, 31
sar edx, s
add edx, eax ; Quotient in EDX
; a == 1
mov eax, m
imul dividend
mov eax, dividend
add edx, eax
shr eax, 31
sar edx, s
add edx, eax ; Quotient in EDX
Code for determining the algorithm (a), multiplier (m), and shift factor (s) is shown in “Derivation of
Algorithm, Multiplier, and Shift Factor for Integer Division by Constants” on page186.
Signed Division by 2
; In: EAX = dividend
; Out: EAX = quotient
cmp eax, 80000000h ; CF = 1 if dividend >= 0.
sbb eax, -1 ; Increment dividend if it is < 0.
sar eax, 1 ; Perform right shift.