为什么 MSB 在 2 的补码乘法中被丢弃？

Question

我很难理解为什么我们在进行 2 的补码乘法时会丢弃 MSB。

我们以101（十进制：-3）和011（十进制：3）为例。算法是这样的：首先我们将数字的长度加倍，然后像在学校用小数做的那样进行通常的乘法运算，然后我们取 (doubled length)*2 = 6 least significant bits.

双倍长度：
```
101 -> 111101
011 -> 000011
```
做乘法： 111101 * 000011 = 10110111（十进制：-73）

正如我们所见，这个结果是错误的。

取 6 个最低有效位（丢弃 2 个最高有效位）。 10110111 -> 110111（十进制：-9）

因此结果神奇地变得正确了。这怎么解释呢？我知道 MSB 有点特殊，我在学校使用的相同规则不能 100% 适合 2 的补码，但是虽然我完全理解学校的乘法规则，但我无法理解 2 的最后一步补码乘法（前两步我理解）。

Answer 1

这只是关于算术的。这在语义上并没有错，因为它实际上是一个正确的 modulo 结果，因为在计算机中对整数的操作会导致丢弃高位，这类似于 k 中的模 2^k位计算机。

首先，您应该知道非加宽乘法对于具有相同位模式的无符号数和 2 的补码有符号数 是相同的。

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₂)^†

可以看具体案例here。对于一般情况，以2个正k-bit数m和n为例。这意味着它们的负值 -m 和 -n 将由 2^k - m 和 2^k - n[ 表示=53=]§ 分别。现在我们将这 2 个负值相乘得到 k 位 结果：

(-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

如果一个数为正数，另一个数为负数，则相同

因此无论将两个位模式视为有符号还是无符号，结果都是一样的。

现在我们有两个n位个无符号数并对它们进行乘法运算，我们将得到一个 2n 位数，因为 n 位数与 m 位数相乘产生 (n+m) 位数。

但是如果我们只关心结果的低n位那么它与具有相同位模式的两个n位无符号数的结果完全相同，如上所述。

所以我们取两个 (n/2) 位有符号数，将它们符号扩展为 n 位（您的第 1^st 步）并进行非加宽乘法（您的 2^nd 步骤）以获得 n 位结果。我们现在所拥有的与从 n/2 位到 n 位的带符号扩大乘法完全相同。

加倍有符号操作数中的位实际上只是使它们与最终结果一样宽因此乘法现在是无符号非加宽而不是有符号加宽和以前一样。

^†_{如果你注意到，有符号和无符号版本的高位也会相互关联，如果你看上面的证明}

^§_{因为 two's complement 是这样定义的：}

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

_{类似于二进制中的1的补码和2的补码，在十进制中我们有9's complement and 10's complement来表示负数，虽然它在日常生活中不常用，但不在本题范围内}

Answer 2

乘法就是重复加法。

当我们将两个 n-bit 数相加时，结果有 (n+1)-bit 因为最多只能有一个继续 MSb。
当我们将两个 n-bit 数相乘时，结果有 (n+n)-bit 因为我们最多将一个数加到自身上 2ⁿ 次，最多产生 2ⁿ 进位，那些需要 log₂(2ⁿ) = n 位。

由于我们通过添加 2n 位 数字来工作，因此我们需要对操作数进行符号扩展以使其大小增加一倍。
这是增加二进制补码大小时的标准规则。

如果我们使用这种低效算法，我们将不需要丢弃任何位。

a和b与b相乘的小学算法=b_k b_k-1 ... b₁ b₀ 利用分布式属性作为 a * b = a * b₀ + a * b₁ * B + a * b₂ * B² + a * b₃ * B³ + ... 其中 B 是数字的底数。

这很有用，因为在二进制中，数字 b_i 要么是 0 要么是 1，因此可以添加一个数字（如果 b_i = 1) 或者不是（如果 b_i) = 0).此外，Bⁱ 的幂是 2 的幂，因此它们可以实现为移位。

现在，由于最后的结果a * b至少要有2n位 每个加数 a * b_i * Bⁱ 的大小必须为 2n 位 。（这在您的问题中也得到了很好的解释）但是，当我们使用移位来执行 Bⁱ 的乘法时，会在 2n 之外引入额外的位必填。
例如：

这些比特只是一个事实的产物，作为人类，在我们完成所有的总和之后丢弃多余的比特比在每个总和中，在我们达到 2n-th 位。

实际上硬件做的是后者，它们有 2n 位 寄存器，它们在其中扩展操作数，并且在移位期间多余的位被丢弃（就像正常移位一样）。累加总和的寄存器也丢弃进位（就像普通加法器一样）。

+-------+   +-------+   +-------+   +-------+   +-------+   +-------+    
|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)  
+-------+

Answer 3

你的乘法完全不正确。你做了一个 unsigned 乘法。换句话说：

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

或十进制 61 x 3 = 183。但是带符号的乘法也需要扩展部分积中的符号位。像这样：

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

现在您可以正确地计算出 -3 x 3 = -9。这种区别对处理器也很重要，比较英特尔处理器上的 MUL 与 IMUL。

为什么 MSB 在 2 的补码乘法中被丢弃？

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

computer-science

multiplication

bit

twos-complement