The rules for binary multiplication are:

In truth table form, the multiplication of two bits, a x b is:

Observe that a x b is identical to the logical `and` operation.

Multiplication of two unsigned binary numbers, X and Y, can be performed
using the *longhand* algorithm:

Y: 1011 X: x 101 ------ 1011 0000 + 1011 -------- 110111

Note that the 0 bits in X contribute a 0 to the product, while the 1 bits in X contribute Y shifted left to align with the corresponding bit in X.

The basis for the longhand algorithm can be understood from the binary representation for unsigned integers. Let X and Y be unsigned n+1 bit integers:

The product XY is given by:

Each nonzero bit in X contributes a term consisting of Y multiplied by a power of 2.

The product of two unsigned n bit numbers can require up to 2n bits since

*Overflow* occurs when the product is larger than n bits.

The longhand multiplication algorithm for n bit unsigned integers can be implemented using n bit addition. Observe that the least significant bit is determined by the first term in the sum. This bit can be stored and the term can be shifted 1 bit to the right in preparation for adding the next term. This process is then repeated n times for n bits.

The longhand algorithm in SAL is:

# # A SAL program to multiply two positive integers using addition and # logical operations. No overflow checking is performed. # .data X: .word # first number to multiply Y: .word # second number to multiply S: .word # the partial sum of products I: .word # bit counter X0: .word # rightmost bit of X Pi: .word # i-th bit of product P: .word # product X times Y .text __start: move I, 32 # initialize counter move S, 0 # initialize partial sum move P, 0 # initialize result get X # input multiplier get Y # input multiplicand loop: and X0, X, 1 # mask rightmost bit of X srl X, X, 1 # shift X right 1 bit beqz X0, shift # if x0=0, shift and get next bit add S, S, Y # add Y to partial sum shift: and Pi, S, 1 # mask rightmost bit of sum or P, P, Pi # store the bit in P srl S, S, 1 # clear sum bit from S ror P, P, 1 # rotate P right 1 bit sub I, I, 1 # decrement shift counter bgtz X, loop # repeat if X nonzero or P, P, S # combine partial sum/result ror P, P, I # final shift put P # output product done

To avoid multiplicative overflow, two 32 bit integers may be multiplied to produce a 64 bit product in two 32 bit words, HI and LO, which hold the most and least significant 32 bits of the product, respectively.

In the HI/LO algorithm, multiplication is performed after splitting the 32 bit numbers to be multiplied into 16 bit HI/LO pairs and performing 32 bit multiplication on the pairs.

An implementation of the HI/LO algorithm in C language is shown below:

The 64 bit HI/LO algorithm may also be implemented in SAL:

The algorithm works without modification for a negative multiplier and a positive multiplicand. It can be extended to work for 2's complement integers. To multiply two negative numbers or a positive multiplier and negative multiplicand, two approaches are possible:

- Convert negative numbers to positive, multiply positive numbers and then convert result to correct sign.
- Sign extend both numbers to 64 bits and perform 64 bit multiplication. The correct result will be found in the least significant 64 bits of the product.

An example of method #2 applied to 4-bit 2's complement integers is shown below. The 4-bit integers 1101 (-3) and 0110 (6) are sign extended to 8 bits before multiplication. The correct result (-18) is found in the rightmost 8 bits.

11111101 (-3) x 00000110 (6) ---------- 00000000 11111101 11111101 00000000 00000000 00000000 00000000 + 00000000 ----------------- 11101110 (-18)

Thu Nov 5 12:25:05 AST 1998