To multiply two binary numbers, we use the same algorithm that is commonly used for decimal numbers. For example:
1010 multiplicand
x 101 multiplier
--------
1010
0000 partial products
+ 1010
----------
110010 product
In the above example (5 times 10 in decimal), each partial product is
the product of one bit of the multiplier times the multiplicand. There
are as many partial products as there are bits in the multiplier, and
there are as many bits in each partial product as there are bits in the
multiplicand.
Note that the partial products resulting from binary multiplication are represented by exactly the same strings of digits as the partial products that would result from the decimal multiplication of one thousand and ten by one hundred and one -- that is, the number base we used had no effect on the computation of the partial products. The number base comes into the picture only when it comes time to add the partial products to make the product.
Note also that, since the only multiplier digits are zero and one, the problem of remembering the multiplication table is eliminated. Each partial product is either zero or a verbatim copy of the multiplier!
In looking for an algorithmic statement of this approach to binary multiplication, it was found that a group of Russian peasants used precisely this method to multiply decimal numbers, and as a result, the binary multiplication algorithm given here is commonly known as the Russian Peasant Algorithm:
set the product to zero
while the multiplier is nonzero
if the multiplier is odd
add the multiplicand to the product
divide the multiplier by two
multiply the multiplicand by two
Converting this to C, we get:
prod = 0;
while (ier) {
if (ier & 1) {
prod += icand;
}
ier >>= 1;
icand <<= 1;
}
This can be converted to an assembly language procedure quite directly:
; procedure to multiply two numbers ; link through R1 ; assumes R2 is used for the stack pointer ; given: multiplier in R3 (ier) ; multiplicand in R4 (icand) ; returns: product in R5 (prod) mult: CLR R5 multlp: TST R3 ; exit loop if ier=zero BZS mulqt SRU R3,1 ; ier /= 2, C = remainder BCR mulno ; if C set (ier odd) ADD R5,R5,R4; add in the partial product mulno: SL R4,1 ; icand *= 2 BR multlp mulqt JUMPS R1 ; returnThis multiply routine has two functional shortcomings: First, it deals with only unsigned integers, and second, it only gives a 32 bit result. In theory, multiplying two 32 bit integers should give a 64 bit result! Nonetheless, for most purposes, it is a fully adequate multiply routine (for example, C and Pascal never give you the full 64 bit result in any implementations I am familiar with)! Finally, it is not a particularly fast multiply routine! There are some elegant (but far larger) algorithms that are much faster.
Many beginning programmers have difficulty figuring out how much commentary to add to their programs. Here are some rules:
In the real world, many programs are read by many people between the time they are written and the time they are discarded. Write comments directed to these people. Who reads programs? Programmers! Programmers who find bugs in the code and must fix it, programmers who are assigned the job of enhancing the code, programmers who are assigned the job of moving the code from one runtime environment to another (from Mac to PC to UNIX to some unanticipated future system).
So, write comments that answer the questions programmers will have about the code, and don't repeat the obvious. Assume that the programmers reading your code and comments know as much as you do about the machine! Comments that simply repeat what anyone with a minimal knowledge of the language can figure out say nothing! Assume your reader knows the language, and use your comments to say what the program text doesn't say.
In addition, comments are very appropriate where they document obscure tricks, places where you've pushed the limits of the language or dredged up obscure features that commonplace programmers are unlikely to know.