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

Question

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

例如，在PowerPC上，毛尔操作码返回一个时钟中32x32位乘法的64位结果的高32位。这正是我要找的，但更轻便。在NVidia数据自动化系统中也有类似的操作码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乘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);
}

Answer 2

我不认为在标准的C/C++中有比你已经拥有的更好的方法来做到这一点。我要做的是编写一个简单的程序集包装器，返回您想要的结果。

并不是询问Windows，而是作为一个示例，尽管Windows有一个API，听起来它可以实现您想做的事情( 32位乘32位，同时获得完整的64位结果)，但它将乘法实现为宏，执行您正在做的事情：

#define UInt32x32To64( a, b ) (ULONGLONG)((ULONGLONG)(DWORD)(a) * (DWORD)(b))

Answer 3

在32位英特尔上，乘法会影响输出的两个寄存器。也就是说，无论您是否愿意，64位都是完全可用的。这仅仅是编译器是否聪明到能够利用它的一个函数。

现代编译器做了令人惊奇的事情，所以我的建议是尝试更多的优化标志，至少在Intel上是这样。您可能认为优化器可能知道处理器从32位乘32位产生64位值。

尽管如此，在某种程度上，我试图让编译器使用模块以及除法结果的红利，但1998年的旧Microsoft编译器还不够聪明，无法实现产生这两种结果的相同指令。