c – 获得64位整数乘法的高位部分

2024-03-24 08:22:28

在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);

解决方法:

如果你正在使用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位数而不会溢出.但是,上述计算的中间结果不会.

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

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关闭,你可以省略进位的计算.

码农公寓