Hacker's Delight

10-1. Signed Division by a Known Power of 2

Apparently, many people have made the mistake of assuming that a shift right signed of k positions divides a number by 2^k, using the usual truncating form of division [GLS2]. It’s a little more complicated than that. The code shown below computes q = n ÷ 2^k, for 1 ≤ k ≤ 31 [Hop].

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, 
shrsi q,t,k         and shift right (signed). 

It is branch-free. It also simplifies to three instructions in the common case of division by 2 (k = 1). It does, however, rely on the machine’s being able to shift by a large amount in a short time. The case k = 31 does not make too much sense, because the number 2³¹ is not representable in ...