Filter
Top Products
186 Integer Optimizations Chapter 8
25112 Rev. 3.06 September 2005
Software Optimization Guide for AMD64 Processors
8.8 Derivation of Algorithm, Multiplier, and Shift
Factor for Integer Division by Constants
The following examples illustrate the derivation of algorithm, multiplier and shift factor for signed
and unsigned integer division.
Unsigned Integer Division
The utility udiv.exe was compiled from the code shown in this section. The utilities provided in this
document are for reference only and are not supported by AMD.
The following code derives the multiplier value used when performing integer division by constants.
The code works for unsigned integer division and for odd divisors between 1 and 2
31
– 1, inclusive.
For divisors of the form d = d' *2n, the multiplier is the same as for d' and the shift factor is s + n.
Example
/* This program determines the algorithm (a), multiplier (m), and
shift factor (s) to be used to accomplish *unsigned* division by
a constant divisor. Compile with MSVC.
*/
#include <stdio.h>
typedef unsigned __int64 U64;
typedef unsigned long U32;
U32 log2(U32 i)
{
U32 t = 0;
i = i >> 1;
while (i) {
i = i >> 1;
t++;
}
return(t);
}
U32 res1, res2;
U32 d, l, s, m, a, r, n, t;
U64 m_low, m_high, j, k;
int main (void)
{
fprintf(stderr, "\n");
fprintf(stderr, "Unsigned division by constant\n");
fprintf(stderr, "=============================\n\n");