Because signed integer division satisfies n ?(-d) = -(n ?d) it is adequate
to generate code for n ?|d| and follow it with an instruction to negate the
quotient. (This does not give the correct result for d
= -2^{W} ^{- 1}, but for this
and other negative powers of 2, you can use the code in Section 10-1,
"Signed Division by a Known Power of 2," on page 155, followed by a
negating instruction.) It will not do to negate the dividend, because of the
possibility that it is the maximum negative number.

It is possible, however, to avoid the negating instruction. The scheme is to compute

Adding 1 if n > 0, however, is awkward (because one cannot simply use the sign bit of n), so the code will instead add 1 if q < 0. This is equivalent because the multiplier m is negative (as will be seen).

The code to be generated is illustrated below for the case W = 32, d = -7.

`li 牋燤,0x6DB6DB6D?Magic num, -(2**34+5)/7 + 2**32. `

`mulhs q,M,n牋牋牋牋 q = floor(M*n/2**32). `

`sub牋 q,q,n牋牋牋牋 q = floor(M*n/2**32) - n. `

`shrsi q,q,2牋牋牋牋 q = floor(q/4). `

`shri?t,q,31牋牋牋?Add 1 to q if `

`add牋 q,q,t牋牋牋牋 q is negative (n is positive). `

` `

`muli?t,q,-7牋牋牋?Compute remainder from `

`sub牋 r,n,t牋牋牋牋 r = n - q*(-7). `

This code is the same as that for division by
+7, except that it uses the negative of the multiplier for +7, and a `sub` rather
than an `add` after the multiply, and the `shri` of 31 must use q rather than n, as
discussed above. (The case of d = +7 could also
use q here, but there would be less parallelism
in the code.) The subtract will not overflow
because the operands have the same sign. This scheme, however, does not always
work! Although the code above for W = 32, d = -7 is correct, the analogous alteration of the
"divide by 3"
code to produce code to divide by -3 does not give the correct result for W = 32, n = -2^{31}.

Let us look at the situation more closely.

Given a word size W
3 and a divisor d, -2^{W} ^{- 1} d -2, we wish to find the
least (in absolute value) integer m and integer
p such that

with -2^{W}
m 0 and
p W.

Proceeding similarly to the case of division
by a positive divisor, let n_{c} be the
most negative value of n such that n_{c} = kd +
1 for some integer k. n_{c}
exists because one possibility is n_{c}
= d + 1. It can be calculated from n_{c} is one of the least |d| admissible
values of n, so

and clearly

Because (14b) must hold for n = -d, and (14a)
must hold for n = n_{c},
we obtain, analogous to (4),

Because m is
to be the greatest integer satisfying (16), it is the next integer less than 2^{p}/d梩hat
is,

Combining this with the left half of (16) and simplifying gives

The proof that the algorithm suggested by
(17) and (18) is feasible and that the product is correct is similar to that
for a positive divisor, and will not be repeated. A difficulty arises, however,
in trying to prove that -2^{W} m 0. To
prove this, consider separately the cases in which d
is the negative of a power of 2, or some other number. For d = -2^{k} it
is easy to show that n_{c} = - 2^{W} ^{- 1} + 1, p = W + k - 1, and m = - 2^{W} ^{- 1} - 1 (which is within
range). For d not of the form -2_{k}, it is straightforward to alter the
earlier proof.

By m(d) we mean the multiplier corresponding to a divisor d. If m(-d) = -m(d), code for division by a negative divisor can be generated by calculating the multiplier for |d|, negating it, and then generating code similar to that of the "divide by 7" case illustrated above.

By comparing (18) with (6) and (17) with (5),
it can be seen that if the value of n_{c}
for -d is the negative of that for d, then m(-d) = -m(d). Hence m(-d) m(d) can occur only when the value of
n_{c} calculated for the negative
divisor is the maximum negative number, -2^{W}
^{- 1}. Such divisors are the negatives of the factors of 2^{W} ^{- 1} + 1. These numbers are
fairly rare, as illustrated by the factorings below (obtained from Scratchpad).

For all these
factors, m(-d) m(d). Proof sketch: For d
> 0 we have n_{c} = 2^{W} ^{- 1} - d. Because rem(2^{W - 1},
d) = d - 1, (6)
is satisfied by p = W
- 1 and hence also by p = W. For d < 0,
however, we have n_{c} = -2^{W} ^{- 1} and rem(2^{W} ^{- 1}, d) = |d| - 1. Hence
(18) is not satisfied for p = W - 1 or for p = W, so p > W.