如何在 C 中获得 64 位整数乘法的上半部分？

获取 64 位整数乘法的上半部分

在 C 中，两个 64 位整数 (uint64_t) 的乘法结果为表示乘积的低 64 位的值，即 (i * j) mod (2^64)。要获取高 64 位，可以采用多种方法。

使用 128 位数字

如果您的编译器支持 128 位整数 (__uint128_t)，则最有效的方法是使用 128 位算术执行乘法并提取高 64 位。

64 位算术的可移植方法

对于不支持的编译器对于 128 位数字，一种可移植的解决方案是将每个 64 位整数拆分为两个 32 位的一半，然后使用 64 位乘法将它们相乘。然后将上半部分和下半部分组合起来计算完整的 128 位乘积。

但是，在使用 64 位算术时，此计算可能会导致溢出。下面的代码提供了一个在计算高 64 位时处理溢出的实现：

uint64_t mulhi(uint64_t a, uint64_t 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;
}

请注意，省略进位位的计算将导致高 64 位值可能偏离 1。

以上是如何在 C 中获得 64 位整数乘法的上半部分？的详细内容。更多信息请关注PHP中文网其他相关文章！