The question is about binary multiplication for negative numbers. Assume we want to multiply -5 * -3 so the result is +15.
1) In the first step, we have to use 2's complement for the inputs.
+5 = 0101 -> -5 = 1011
+3 = 0011 -> -3 = 11012) We follow the simple pencil-and-paper method and we have to note the sign extension. For the sake of clarity I put the signs extensions in []
1011 * 1101 ---------------- [1] [1] [1] 1 0 1 1 [0] [0] 0 0 0 0 [1] 1 0 1 1 1 0 1 1 + ------------------------------ c7 c6 c5 c4 c3 c2 c13) summing the columns show that
c1 = 1 + 0 + 0 + 0 = 1
c2 = 1 + 0 + 0 + 0 = 1
c3 = 0 + 0 + 1 + 0 = 1
c4 = 1 + 0 + 1 + 1 = 1 (carry 1 to c5)
c5 = 1(carry) + 1(sign) + 0 + 0 + 1 = 1 (carry 1 to c6)
c6 = 1(carry) + 1(sign) + 0(sign) + 1 + 0 = 1 (carry 1 to c7)
c7 = 1(carry) + 1(sign) + 0(sign) + 1(sign) + 1 = ???Actually c7 = 100 but we have to represent only one digit in c7. So does that mean
c7 = 0 (carry 10)?? Usually the final carry bit is only one digit. More than that, the final number is not equal to +15. Where did I make the mistake?
4 Answers
$\begingroup$I believe the answer given by "Wildcard" does not fully answer this question. He does not extend the sign before multiplication, which could cause confusion in new viewers. Furthermore, you don't "multiply forever to wind up with infinite bits", the signs are simply extended beforehand. So this should look better:
1 1 1 1 1 0 1 1 = -5 * 1 1 1 1 1 1 0 1 = -3
-------------------------------------------- 1 1 1 1 1 0 1 1 0 0 0 0 0 0 0 0 | 1 1 1 1 1 0 1 1 | 1 1 1 1 1 0 1 1 | 1 1 1 1 1 0 1 1 | | 1 1 1 1 1 0 1 1 | | 1 1 1 1 1 0 1 1 | |
1 1 1 1 1 0 1 1 | |
-------------------------------------------- discarded| 0 0 0 0 1 1 1 1 = +15The bits at the end are discarded because the number is 8 bit.
Reference and Further Reading:
$\endgroup$ 2 $\begingroup$ 1011 * 1101 ----------------
[1][1] [1] [1] 1 0 1 1 [0] [0] 0 0 0 0
[1][1] 1 0 1 1
[1] 1 0 1 1 +
1 0 1 1
... 1 1 ------------------------------ c7 c6 c5 c4 c3 c2 c1Does this clarify it?
If you keep going to the left, you will wind up carrying infinitely many bits. But that's as it should be. The actual answer on the right winds up as ...01111 when you include the 1011 entry ending in column 5. The more 1011 entries you include (ending at c6, c7, etc.) the more zeros you'll have at the start of your answer.
I don't know any textbook answer for where to stop going to the left, but you can at least see it conceptually from the above.
$\endgroup$ $\begingroup$When you multiply two negative numbers,in the last term you have to write 2's complement of the first number.In this case 2's complement of 1011 is 0101. I put 2's complement in ().
1011 * 1101 ---------------------------------- [1] [1] [1] [1] 1 0 1 1 [0] [0] [0] 0 0 0 0 x [1] [1] 1 0 1 1 x x [0] (0 1 0 1) x x x + ---------------------------------- 0 0 0 0 1 1 1 1 Discard the remaining bit as we need answer in 8-bit if we keep moving to the left we only get more 0 on the left of number.
$\endgroup$ $\begingroup$As @Hamza Bhati mentioned,
When you multiply two negative numbers, in the last term you have to write 2's complement of the first number.
I'd like to explain the reason: taking your example, 1011x1101=1011x(1000+0101)=1011x1000+1011x0101, you shall use normal multiplication on the part of 0101, while you shall use 2's complement on the part of 1011x1000 and add them together.
