解释为什么“负”无符号数相乘会产生正确的结果

Question

我根本无法理解 4294967294 与 4294967292 相乘如何得出 8。

代码示例：

#include <stdio.h>

unsigned int a = -2;
unsigned int b = -4;

int main()
{
    printf( "a     = %u\n"
            "b     = %u\n"
            "a * b = %u\n", 
            a, b, a*b
    );

    return 0;
}

请提供有关这些位发生的情况及其原因的逐步解释。如果可能，请提供证据证明这在 C99 或 C11 标准下是合法的。评论这是否会通过“代码审查”。

Answer 1

令w为 中的位数unsigned int。那么 an 能表示的最大数字unsigned int是 2 ^w \xe2\x88\x921，比它多 1 就是 2 ^w。

\n

C 2018 6.2.5 9 说：

\n

\n

\xe2\x80\xa6 涉及无符号操作数的计算永远不会溢出，因为无法由结果无符号整数类型表示的结果会按比结果类型可以表示的最大值大 1 的数字进行减模。

\n

\n

和 6.3.1.3 1 和 2 说，关于转换为无符号整数类型：

\n

\n

\xe2\x80\xa6 如果该值可以用新类型表示，则它不变。

\n

否则，\xe2\x80\xa6 通过重复加或减比新类型可以表示的最大值大一的方式来转换该值，直到该值在新类型的范围内。

\n

\n

因此，任何转换或计算都会包含unsigned int模 2 ^w。

\n

考虑unsigned int a = -2;。\xe2\x88\x922 无法用 表示，因此通过添加 2 ^wunsigned int进行调整。这会产生 2 ^w \xe2\x88\x922，这是可表示的。（如果w为 32，则 2 ^w \xe2\x88\x922 为 4,294,967,294。）

\n

类似地，在 中unsigned int b = -4;，2 ^w被添加到 \xe2\x88\x924，并被b初始化为 2 ^w \xe2\x88\x924（如果w则为 4,294,967,292）为 32，则为 4,294,967,292）。

\n

现在考虑一下a*b。a是 2 ^w \xe2\x88\x922 和b2 ^w \xe2\x88\x924，因此数学结果将是 (2 ^w \xe2\x88\x922) \xe2\x80\xa2 (2 ^w \xe2\x88\ x924) = 2 ^w \xe2\x80\xa22 ^w + 2 ^w \xe2\x80\xa2\xe2\x88\x924 + \xe2\x88\x922\xe2\x80\xa22 ^w + \xe2\x88\x924\xe2 \x80\xa2\xe2\x88\x922 = 2 ^{2 w} \xe2\x88\x92 6\xe2\x80\xa22 ^w + 8。

\n

该值太大而无法用 表示，因此以 2 ^wunsigned int为模进行减小。观察 2 ^{2 w} \xe2\x88\x92 6\xe2\x80\xa22 ^{w是 2 w}的倍数，因此减少 2 ^{2 w} \xe2\x88\x92 6\xe2\x80\xa22 ^w + 8 modulo 2 ^w产量 8。

\n

要了解这些位发生了什么，请考虑数学结果 2 2 ^{w \} xe2\x88\x92 6\xe2\x80\xa22 ^w + 8。这是 (2 ^w \xe2\x88\x92 6)\xe2\ x80\xa22 ^w + 8。在二进制中，(2 ^w \xe2\x88\x92 6)\xe2\x80\xa22 ^{w是 2 w} \xe2\x88\x92 6 左移 2 ^w位的二进制数。所以它以w 0 位结束。为此，我们添加了八个。因此，如果我们采用 2 ^{2 w} \xe2\x88\x92 6\xe2\x80\xa22 ^w + 8 的二进制数字并丢弃高位，仅保留低w位，则剩下 8 的二进制数字。

\n

例如，当w = 32 时， 2 ⁶⁴ \xe2\x88\x92 6\xe2\x80\xa22 ³² + 8 为 11111111 11111111 11111111 11111010 00000000 00000000 00000000 00001000 ₂。低32位是 00000000 00000000 00000000 00001000 ₂，代表8。

\n