如何在 C 中提取 64 位整数乘法的高位部分？

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

在 C 中，两个 64 位无符号整数 (uint64_t) 相乘的结果在仅包含乘积下部的 uint64_t 中（即 (i * j) mod 2^64）。如果您想获得乘法的较高部分，这里有一些有效的方法：

使用 128 位数字

如果您的编译器支持 128 位数字 (例如，在 GCC 中使用 __uint128_t），您可以执行 128 位乘法并提取高 64 位。此方法可能是最有效的。

乘法分解

如果您的编译器不支持 128 位数字，您可以将每个 64 位整数分解为以下部分：

• a = (a_hi
• b = (b_hi

其中a_hi、a_lo、b_hi 和 b_lo 是 32 位无符号整数。

算法

要计算乘法的高位部分 (a_hi * b_hi)，您可以请按照以下步骤操作：

1. 计算乘积 a_hi b_hi、a_hi b_lo、b_hi a_lo 和 a_lo b_lo。
2. 添加乘积a_hi b_hi 以及 a_hi b_lo 和 b_hi * a_lo 之和的高 32 位。
3. 将步骤 2 的结果添加到 a_lo * b_lo 的高 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;

uint64_t a_x_b_hi = a_hi * b_hi;
uint64_t a_x_b_mid = (a_hi * b_lo) >> 32;
uint64_t b_x_a_mid = (b_hi * a_lo) >> 32;
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 + b_x_a_mid + carry_bit;

return multhi;

请注意，此代码可能并不完全准确，但它提供了乘法较高部分的良好近似值。

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