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

检索 64 位整数乘法的高位

在 C 中，将两个 64 位无符号整数 (uint64_t) 相乘结果产生一个表示乘法低阶位的值，有效地给出结果模2^64。这就提出了如何获取高位位的问题，这对于某些计算来说通常是必需的。

实现方法

1. 128-位乘：

如果您的编译器支持128 位数字 (__uint128_t)，执行 128 位乘法并提取高 64 位是获取高位的最有效方法。

2. 32 位乘法和64 位累加：

如果不支持 128 位数字，一个可移植且简单的解决方案是将每个 64 位数字分解为两个 32 位数字，对它们执行 32 位乘法，并仔细累加 64 位部分乘积，注意避免整数溢出。

汇编指令：

对于某些架构，例如x86 中，有专门的汇编指令（例如 MULH）被设计来执行此类 64 位整数乘法。但是，在 C 中使用这些指令需要汇编编程知识，并且可能不如前面提到的 C 方法那么可移植。

示例实现：

以下 C 代码实现 32 位乘法和 64 位累加方法：

uint64_t mulhi(uint64_t a, uint64_t b) {
  uint32_t a_lo = (uint32_t)a;
  uint32_t a_hi = a >> 32;
  uint32_t b_lo = (uint32_t)b;
  uint32_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 + a_lo * b_hi; // Avoid overflow
  uint64_t b_x_a_mid = b_hi * a_lo;
  uint64_t a_x_b_lo = a_lo * b_lo;

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

  return multhi;
}

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