Hacker's Delight

10-3. Signed Division and Remainder by Non-Powers of 2

The basic trick is to multiply by a sort of reciprocal of the divisor d, approximately 2³²/d, and then to extract the leftmost 32 bits of the product. The details, however, are more complicated, particularly for certain divisors such as 7.

Let us first consider a few specific examples. These illustrate the code that will be generated by the general method. We denote registers as follows:

n - the input integer (numerator)

M - loaded with a “magic number”

t - a temporary register

q - will contain the quotient

r - will contain the remainder

Divide by 3

 li M,0x55555556 Load magic number, (2**32+2)/3. mulhs q,M,n q = floor(M*n/2**32). shri t,n,31 Add 1 to q if add q,q,t n is negative. muli ...