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 the machine. Nevertheless, the code does produce the correct result in that case (which is q = -1 if n = -231 and q = 0 for all other n).

To divide by -2k, the above code may be followed by a negate instruction. There does not seem to be any better way to do it.

The more straightforward code for dividing by 2k is

牋牋牋 bge牋 n,label牋牋牋 Branch if n >= 0. 
牋牋牋燼ddi?n,n,2**k-1牋?Add 2**k - 1 to n, 
label?shrsi n,n,k牋牋牋牋 and shift right (signed). 

This would be preferable on a machine with slow shifts and fast branches.

PowerPC has an unusual device for speeding up division by a power of 2 [GGS]. The shift right signed instructions set the machine's carry bit if the number being shifted is negative and one or more 1-bits are shifted out. That machine also has an instruction for adding the carry bit to a register, denoted addze. This allows division by any (positive) power of 2 to be done in two instructions:

shrsi q,n,k 
addze q,q 

A single shrsi of k positions does a kind of signed division by 2k that coincides with both modulus and floor division. This suggests that one of these might be preferable to truncating division for computers and HLL's to use. That is, modulus and floor division mesh with shrsi better than does truncating division, permitting a compiler to translate the expression n/2 to an shrsi. Furthermore, shrsi followed by neg (negate) does modulus division by -2k, which is a hint that maybe modulus division is best. (However, this is mainly an aesthetic issue. It is of little practical significance because division by a negative constant is no doubt extremely rare.)