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 2k, using the usual truncating form of division [GLS2]. It’s a little more complicated than that. The code shown below computes q = n ÷ 2k, 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 231 is not representable in ...

Get Hacker's Delight now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.