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

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

在 C 中，如果 i 和 j 是 64 位无符号整数，则 i * j 产生其乘积的低 64 位，即 (i * j) mod 2^64。要获得乘积的较高部分，请考虑以下方法：

使用 128 位乘法：

如果编译器支持 128 位整数（例如 __uint128_t ），执行 128 位乘法并提取高 64 位是最有效的方法。

YAK 的方法（使用 32 位乘法）：

这涉及将每个 64 位整数分成两个 32 位半数，使用 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 multhi = a_hi * b_hi + (a_hi * b_lo >> 32) + (b_hi * a_lo >> 32) + a_lo * b_lo;

处理溢出：

但是，上述计算执行的是 128 位运算，可能会导致溢出。为了在限制为 64 位算术时处理此问题，以下实现会针对溢出进行调整：

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 = ((uint32_t)a_x_b_mid + (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;

注意： 如果可以接受高 64 位中的 1 位错误，则进位位的计算可以省略。

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