Page 269 - ARM 64 Bit Assembly Language

258 Chapter 8

two (a shift operation), division by a constant could be performed using only integer opera-
tions with a more efficient multiply replacing the (usually) very slow divide.

This section presents an alternate way to achieve the same results, by treating division by an
integer constant as an application of fixed point multiplication. Again, the integer constant
divisor is converted into its reciprocal, but this time the process is considered from the view-
point of fixed-point mathematics. Both methods will achieve exactly the same results, but
some people tend to grasp the fixed point approach more easily than the purely integer ap-
proach.

When writing code to divide by a constant, the programmer must strive to achieve the largest
number of significant bits possible, while using the shortest (and most efficient) representation
possible. On modern computers, this usually means using 32-bit integers and integer multiply
operations which produce 64-bit results. That would be extremely tedious to show in a text-
book, so the principals will be demonstrated here using 8-bit integers and an integer multiply
which produces a 16-bit result.

8.4.4.1 Division by constant 23

Suppose we want efficient code to calculate x ÷ 23 using only 8-bit signed integer multiplica-
tion. The reciprocal of 23, in binary, is

1
R = = 0.0000101100100001011... 2 .
23

If we store R as an S(1,11), it would look like this:

Note that in this format, the reciprocal of 23 has five leading zeros. We can store R in eight
bits by shifting it left to remove some of the leading zeros. Each shift to the left changes the
format of R. After removing the first leading zero bit, we have: