Page 201 - ARM 64 Bit Assembly Language

Integer mathematics 189

− 023 977 11101001
− 015 = − 985 = + 11110001
− 038 − 1962 111011010

7.2 Binary multiplication

Many processors have hardware multiply instructions. However hardware multipliers re-
quire a large number of transistors, and consume significant power. Processors designed for
extremely low power consumption or very small size usually do not implement a multiply in-
struction, or only provide multiply instructions that are limited to a small number of bits. On
these systems, the programmer must implement multiplication using basic data processing in-
structions. Even when a hardware multiplier is available, there are some techniques available
which may achieve higher performance.

7.2.1 Multiplication by a power of two

If the multiplier is a power of two, then multiplication can be accomplished with a shift to
0
1
2
3
the left. Consider the four bit binary number x = x 3 × 2 + x 2 × 2 + x 1 × 2 + x 0 × 2 ,
where x n denotes bit n of x.If x is shifted left by one bit, introducing a zero into the least
4 3 2 1 0
significant bit, then it becomes x 3 × 2 + x 2 × 2 + x 1 × 2 + x 0 × 2 + 0 × 2 =
3 2 1 0 −1
2 x 3 × 2 + x 2 × 2 + x 1 × 2 + x 0 × 2 + 0 × 2 . Therefore, a shift of one bit to the left
is equivalent to multiplication by two. This argument can be extended to prove that a shift left
n
by n bits is equivalent to multiplication by 2 .

7.2.2 Multiplication of two variables

Most techniques for binary multiplication involve computing a set of partial products and then
summing the partial products together. This process is similar to the method taught to primary
schoolchildren for conducting long multiplication on base ten integers, but has been modified
here for application to binary. The method typically taught in school for multiplying decimal
numbers is based on calculating partial products, shifting them to the left and then adding
them together. The most difficult part is to obtain the partial products, as that involves mul-
tiplying a long number by one base ten digit. The following example shows how the partial
products are formed.