c - 得到两个无符号整数相乘的高 32 位 (HW)

Question

我正在阅读 CSAPP 并尝试完成作业问题。假设 w = 32，2.75 是关于通过将两个 32 位无符号整数相乘得到高 32 位。给定函数 int signed_high_prod(int x, int y)它计算 x 的高 32 位。 y 表示 x 和 y 为补码形式的情况。 int signed_high_prod(int x, int y)应该用于实现 unsigned int unsigned_high_prod(unsigned x, unsigned y) .

通过谷歌搜索我找到了x'.y' = x.y + x.y_31.2^32 + y.x_31.2^32 + x_31.y_31.2^64 , 其中 x' 和 y' 分别是 x 和 y 的无符号形式。

还是没看懂

unsigned unsigned_high_prod(unsigned x, unsigned y){
    unsigned p = (unsigned) signed_high_prod((int) x, (int) y)
    if((int) x < 0){
        p += y;
    }
    if((int) y < 0){
        p += x;
    }
    return p;
}

为什么最后一项对结果没有影响？为什么什么时候x < 0所以x_31 = 1 , 加上 y ？和y一样.

Answer 1

要将带符号的 2 的补码 32 位整数转换为无符号的 32 位整数，如果它是负数，我们将 2³² 添加到它的值。

signed_high_prod 执行有符号乘法并返回乘积的第 63 位到第 32 位。我们希望 unsigned_high_prod 对无符号乘法执行相同操作并利用 signed_high_prod 然后补偿无符号和有符号乘法之间的差异。

Let N(i) = { 1, i < 0
           { 0, i >= 0

Let U(i) = i + N(i)·2³² { −2³¹ <= i < 2³¹ }

然后:

U(x)·U(y) = (x + N(x)·2³²)·(y + N(y)·2³²)
          = x·y + x·N(y)·2³² + N(x)·2³²·y + N(x)·2³²·N(y)·2³²
          = x·y + x·N(y)·2³² + y·N(x)·2³² + N(x)·N(y)·2⁶⁴

⌊U(x)·U(y)/2³²⌋ = ⌊x·y/2³²⌋ + x·N(y) + y·N(x) + N(x)·N(y)·2³²

由于无符号 32 位整数的算术将以 2³² 为模执行，我们有:

⌊U(x)·U(y)/2³²⌋ mod 2³²  = (⌊x·y/2³²⌋ + x·N(y) + y·N(x) + N(x)·N(y)·2³²) mod 2³²
                         = (⌊x·y/2³²⌋ + x·N(y) + y·N(x)) mod 2³²

我相信这说明了您的 unsigned_high_prod 函数执行的计算。