c++ - 获取 64 位整数乘法的高位部分

Question

在 C++ 中，这样说:

uint64_t i;
uint64_t j;

然后 i * j 将产生一个 uint64_t，它的值是 i 和 j< 之间相乘的下半部分，即 (i * j) mod 2^64。 现在，如果我想要乘法的较高部分怎么办？我知道在使用 32 位整数时存在类似的汇编指令，但我对汇编一点也不熟悉，所以我希望得到帮助。

什么是最有效的方法来制作类似的东西:

uint64_t k = mulhi(i, j);

Answer 1

如果您使用 gcc 并且您拥有的版本支持 128 位数字(尝试使用 __uint128_t)，那么执行 128 乘法并提取高 64 位可能是获得结果的最有效方法。

如果你的编译器不支持 128 位数字，那么 Yakk 的回答是正确的。但是，对于一般消费来说，它可能太简短了。特别是，实际实现必须小心溢出 64 位整数。

他提出的简单且可移植的解决方案是将 a 和 b 分别分解为 2 个 32 位数字，然后使用 64 位乘法运算将这些 32 位数字相乘。如果我们写:

uint64_t a_lo = (uint32_t)a;
uint64_t a_hi = a >> 32;
uint64_t b_lo = (uint32_t)b;
uint64_t b_hi = b >> 32;

那么很明显:

a = (a_hi << 32) + a_lo;
b = (b_hi << 32) + b_lo;

和:

a * b = ((a_hi << 32) + a_lo) * ((b_hi << 32) + b_lo)
      = ((a_hi * b_hi) << 64) +
        ((a_hi * b_lo) << 32) +
        ((b_hi * a_lo) << 32) +
          a_lo * b_lo

如果计算是使用 128 位(或更高)算术执行的。

但是这个问题需要我们使用 64 位算术来执行所有的计算，所以我们不得不担心溢出。

由于 a_hi、a_lo、b_hi 和 b_lo 都是无符号 32 位数字，它们的乘积将适合无符号 64 位数字而不会溢出。但是，上述计算的中间结果不会。

当数学必须以 2^64 为模执行时，以下代码将实现 mulhi(a, b):

uint64_t    a_lo = (uint32_t)a;
uint64_t    a_hi = a >> 32;
uint64_t    b_lo = (uint32_t)b;
uint64_t    b_hi = b >> 32;

uint64_t    a_x_b_hi =  a_hi * b_hi;
uint64_t    a_x_b_mid = a_hi * b_lo;
uint64_t    b_x_a_mid = b_hi * a_lo;
uint64_t    a_x_b_lo =  a_lo * b_lo;

uint64_t    carry_bit = ((uint64_t)(uint32_t)a_x_b_mid +
                         (uint64_t)(uint32_t)b_x_a_mid +
                         (a_x_b_lo >> 32) ) >> 32;

uint64_t    multhi = a_x_b_hi +
                     (a_x_b_mid >> 32) + (b_x_a_mid >> 32) +
                     carry_bit;

return multhi;
                                              

正如 Yakk 所指出的，如果你不介意在高 64 位中被 +1，你可以省略进位的计算。