Senior: Binary Multiplication Section A

Problem: Create a program that will perform binary multiplication using the "shift and add" method.

Although it might not seem so at first glance, the "shift and add" algorithm is logically identical to the base ten multiplication you learned in elementary school for multiplying numbers higher than ten. We will learn about this algorithm by going through an example in the box on the right.

Take the example of 9 × 6. First, convert each number to binary. This yields the two operands shown. The accumulator, or temporary variable, column will hold the intermediate work.

Start the accumulator at 0 and look at the leftmost bit of the six, the second operand. This bit is a one. Whenever the working bit in the second operand is a one, we add the first operand to the accumulator (Add 1). Since there are more bits in the second operand, we look at the next leftmost bit. Whenever we move over to the next bit, we must also shift the accumulator once to the left (Shift 1).

The current working bit is also a one, which means add the first operand to the accumulator again (Add 2). There are more bits, so shift again (Shift 2). Now, the working bit is a zero, so we just add zero – in other words do nothing – to the accumulator (Add 3). When we check for more bits, we see that we are at the end of the second operand and therefore do not shift anymore. We are done and the result is the binary version of 54, which is the answer we were looking for.

To summarize, simply start at the left of the second operand. Moving to the right, if the current bit is a one, add the first operand. If it is a zero, do nothing. Each time you move to the next bit, shift the accumulator.

Input: Your program must accept two numbers, each between 0 and 255 inclusive (8 bits, unsigned)

Output: The program must display the binary equivalents of the two numbers first. Then, using the operands as described above, it should display the accumulator at each stage and label the stages. Operands should be left at eight bits (i.e., do not remove leading zeros) and the accumulator should be sixteen bits wide.

Sample:

Enter First Operand: 25

Enter Second Operand: 53

25 = 00011001, 53 = 00110101

Start : 0000000000000000

Add 1 : 0000000000000000

Shift 1: 0000000000000000

Add 2 : 0000000000000000

Shift 2: 0000000000000000

Add 3 : 0000000000011001

Shift 3: 0000000000110010

Add 4 : 0000000001001011

Shift 4: 0000000010010110

Add 5 : 0000000010010110

Shift 5: 0000000100101100

Add 6 : 0000000101000101

Shift 6: 0000001010001010

Add 7 : 0000001010001010

Shift 7: 0000010100010100

Add 8 : 0000010100101101

Result : 0000010100101101 = 1325

Again (y/n): Y

Enter First Operand: 255

Enter Second Operand: 255

255 = 11111111, 255 = 11111111

Start : 0000000000000000

Add 1 : 0000000011111111

Shift 1: 0000000111111110

Add 2 : 0000001011111101

Shift 2: 0000010111111010

Add 3 : 0000011011111001

Shift 3: 0000110111110010

Add 4 : 0000111011110001

Shift 4: 0001110111100010

Add 5 : 0001111011100001

Shift 5: 0011110111000010

Add 6 : 0011111011000001

Shift 6: 0111110110000010

Add 7 : 0111111010000001

Shift 7: 1111110100000010

Add 8 : 1111111000000001

Result : 1111111000000001 = 65025

Again (y/n): N


Last Modified:- 1999, February 11, 03:38 PM by M. Smith