Why MSB's are discarded during 2's complement multiplication?

Question

I have a trouble with understanding why we discard MSB when we do multiplication of 2's complements numbers.

Let's take 101 (decimal: -3) and 011 (decimal: 3) for example. Algorithm goes like this: first we double length of our numbers, then we do usual multiplication as we did in school with decimals, then we take (doubled length)*2 = 6 least significant bits.

1. Double lengths:

   101 -> 111101
   011 -> 000011
   

2. Do multiplication: 111101 * 000011 = 10110111 (decimal: -73)

As we see, this result is wrong.

3. Take 6 least significant bits (drop 2 most significant bits). 10110111 -> 110111 (decimal: -9)

And so result became magically right. How can this be explained? I understand that MSB is kind of special and the same rules I've used in school cannot be 100% suitable for 2's complements, but while I fully understand school rules of multiplication, I can't wrap my head around the last step of 2's complement multiplication (first two steps I understand).

Answer 1

Your multiplication is simply incorrect. You did an unsigned multiplication. In other words this:

    111101  
    000011 x
    ------ 
    111101
   111101
  000000
 000000
000000     +
----------
0010110111

Or in decimal 61 x 3 = 183. But a signed multiplication requires extending the sign bit in the partial products as well. Like this:

    111101  
    000011 x
    ------ 
1111111101
111111101 
00000000
0000000
000000     +
----------
1111110111

So now you correctly compute -3 x 3 = -9. This distinction matters for processors as well, compare MUL vs IMUL on Intel processors.

Answer 2

That's just about arithmetics. It's not semantically wrong because it's actually a correct modulo result, as operations on integers in computers result in the discarding of the high bits which is similar to modulo 2^k in a k-bit computer.

---

First, you should know that non-widening multiplication is the same for both unsigned and 2's complement signed number with the same bit pattern.

For example: 1001₂ x 0011₂.

• Treating as unsigned we have 9 x 3 = 27 (0001 1011₂)
• Treat them as signed we have -7 x 3 = -21 (1110 1011₂)^†

You can see a specific case here. For the general case take 2 positive k-bit numbers m and n for example. That means their negative values -m and -n will be represented by 2^k - m and 2^k - n^§ respectively. Now we multiply those 2 negative values to get a k-bit result:

(-m)(-n) mod 2^k
= (2^k - m)(2^k - n) mod 2^k
= [2^2k -2^k(m+n) + mn] mod 2^k
= mn mod 2^k
=(-m)(-n) mod 2^k

The same in case one number is positive and the other is negative

So regardless of treating two bit patterns as signed or unsigned, the result is still the same.

---

Now we have two n-bit unsigned numbers and do multiplication on them, we'll get a 2n-bit number, because multiplying an n-bit number and an m-bit number producing an (n+m)-bit result.

But if we only care about the low n-bits of the result then it's exactly the same as the result of two n-bit unsigned numbers with the same bit pattern, as proved above.

So we take two (n/2)-bit signed numbers, sign-extend them to n-bits (your 1^st step) and do non-widening multiplication (your 2^nd step) to get an n-bit result. What we have now is exactly the same as signed widening multiplication from n/2 bits to n bits.

Doubling the bits in the signed operands is effectively just making them as wide as the final result so that the multiplication is now an unsigned non-widening instead of a signed widening one as before.

^†_{If you notice, the high bits of the signed and unsigned versions will have relation to each other too, if you look at the proof above}

^§_{Because that's how two's complement is defined:}

The two's complement of an N-bit number is defined as the complement with respect to 2^N; in other words, it is the result of subtracting the number from 2^N

_{Similar to 1's complement and 2's complement in binary, in decimal we have 9's complement and 10's complement to represent negative numbers although it's not used in daily life and is out of scope of this problem}

Answer 3

Multiplication is just repeated addition.

When we sum two n-bit numbers the result has (n+1)-bit as there can be at most one carry on the MSb.
When we multiply two n-bit numbers the result has (n+n)-bit as we add a number to itself at most 2ⁿ times and that produces at most 2ⁿ carries and those takes log₂(2ⁿ) = n bits.

Since we work by adding 2n-bit numbers we need to sign extend the operands to twice their size.
This is a standard rule when growing the size of two's complement number.

If we were to use this inefficient algorithm we won't need to throw away any bit.

---

The grade school algorithm for multiplying a and b with b = b_k b_k-1 ... b₁ b₀ exploits the distributive property as a * b = a * b₀ + a * b₁ * B + a * b₂ * B² + a * b₃ * B³ + ... where B is the base of the numbers.

This is useful as in binary a digit b_i is either 0 or 1 so that a number is either added (if b_i = 1) or it isn't (if b_i) = 0). Furthermore the powers Bⁱ are powers of two so they can be implemented as a shift.

Now, since the final result a * b must have at least 2n-bit each of the addend a * b_i * Bⁱ must be of size 2n-bit. (again this is well explained in your question) However when we use a shift to perform the multiplication by Bⁱ that introduces additional bit beyond the 2n required.
For example:

  |
  111 111
  |   011
  -------
  |    11 
  |   11
  |  11
  |11
  11
 11
  |

These bits are just an artifact of the fact that, as humans, it's more simple to just discard the surplus of bits after we have done all the sums rather than, in each sum, stopping after we reach the 2n-th bit.

In practice hardware do the latter, they have 2n-bit registers where they extend the operands and during the shifting the surplus bit are discarded (just like a normal shift). The register that accumulates the sums also discard the carry (just like a normal adder).

+-------+   +-------+   +-------+   +-------+   +-------+   +-------+    
|000 011| + |000 110| + |001 100| + |011 000| + |110 000| + |100 000|
+-------+   +-------+   +-------+   +-------+   +-------+   +-------+

=

+-------+
|111 101| Correct result with no bits discarded (but for the sums carries)  
+-------+