2.3.4 无符号乘法

2.3.4 无符号乘法

范围在 0 ≤ x, y ≤ 2^w - 1 内的整数 x 和 y 可以被表示为 w 位的无符号数，但是它们的乘积 x · y 的取值范围为 0 到 (2^w - 1)² = 2^2w - 2^w+1 + 1 之间。这可能需要 2w 位来表示。不过，C 语言中的无符号乘法被定义为产生 w 位的值，就是 2w 位的整数乘积的低 w 位表示的值。我们将这个值表示为 x *^u_w y。

将一个无符号数截断为 w 位等价于计算该值模 2^w，得到：

原理：无符号数乘法

对满足 0 ≤ x, y ≤ UMax_w 的 x 和 y 有：

x *^u_w y = (x · y) mod 2^w　（2.16）