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

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

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 2k, 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 graphics/10icon02.gifand 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 2k - 1 for n < 0 and 0 for n 0 can be constructed from



which adds only one instruction.