10-2 Signed Remainder from Division by a Known Power of 2

If both the quotient and remainder of n ?2^k are wanted, it is simplest to compute the remainder r from r = q * 2^k - n. This requires only two instructions after computing the quotient q:

shli?r,q,k 
sub   r,r,n 

To compute only the remainder seems to require about four or five instructions. One way to compute it is to use the four-instruction sequence above for signed division by 2^k, followed by the two instructions shown immediately above to obtain the remainder. This results in two consecutive shift instructions that can be replaced by an and, giving a solution in five instructions (four if k = 1):

shrsi t,n,k-1       Form the integer 
shri?t,t,32-k    ?2**k - 1 if n < 0, else 0. 
add   t,n,t         Add it to n, 
andi?t,t,-2**k     clear rightmost k bits, 
sub   r,n,t         and subtract it from n. 

Another method is based on

To use this, first compute and then

(five instructions) or, for k = 1, since (-n) & 1 = n & 1,

(four instructions). This method is not very good for k > 1 if the machine does not have absolute value (computing the remainder would then require seven instructions).

Still another method is based on

This leads to

(five instructions for k > 1, four for k = 1).

The above methods all work for 1 k 31.

Incidentally, if shift right signed is not available, the value that is 2^k - 1 for n < 0 and 0 for n 0 can be constructed from

which adds only one instruction.