c++ - 高效计算 32 位整数乘法的高阶位

Question

许多 CPU 都有单一的汇编操作码，用于返回 32 位整数乘法的高位。通常将两个 32 位整数相乘会产生 64 位结果，但如果将其存储在 32 位整数中，则会被截断为低 32 位。

例如，在 PowerPC 上，mulhw操作码返回一个时钟内 32x32 位乘法的 64 位结果的高 32 位。这正是我正在寻找的，但更便携。 NVidia CUDA 中有一个类似的操作码 umulhi()。

在 C/C++ 中，是否有一种有效的方法来返回 32x32 乘法的高阶位？目前我通过转换为 64 位来计算它，例如:

unsigned int umulhi32(unsigned int x, unsigned int y)
{
  unsigned long long xx=x;
  xx*=y;
  return (unsigned int)(xx>>32);
}

但这比常规的 32 x 32 乘法慢了 11 倍以上，因为即使是乘法，我也使用了过度的 64 位数学。

有没有更快的方法来计算高阶位？

这显然不是最好用 BigInteger 库来解决(这太过分了并且会产生巨大的开销)。

SSE 好像有PMULHUW ，这是一个 16x16 -> 前 16 位版本，但不是我正在寻找的 32x32 -> 前 32 位版本。

Answer 1

gcc 4.3.2，具有 -O1 优化或更高版本，完全按照您向 IA32 程序集显示的方式翻译您的函数，如下所示:

umulhi32:
        pushl   %ebp
        movl    %esp, %ebp
        movl    12(%ebp), %eax
        mull    8(%ebp)
        movl    %edx, %eax
        popl    %ebp
        ret

这只是执行单个 32 位 mull 并将结果的高 32 位(来自 %edx)放入返回值。

这就是你想要的，对吧？听起来您只需要在编译器上进行优化；)您可以通过消除中间变量将编译器推向正确的方向:

unsigned int umulhi32(unsigned int x, unsigned int y)
{
  return (unsigned int)(((unsigned long long)x * y)>>32);
}