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