Hacker's Delight

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 ...