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

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

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

在C / C ++中，有没有一种有效的方法来返回32×32乘法的高阶位？ 目前我通过转换为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 ，16×16 – > 16位版本，但不是32×32 – > 32版本，就像我在寻找。

Answer 1

gcc 4.3.2，带-O1优化或更高版本，将您的function完全翻译为IA32程序集，如下所示：

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

这只是进行一次32位调整，并将结果的高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（在获得完整的64位结果时32乘32位乘法），它实现了乘法作为宏做你正在做的事情：

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

Answer 3

在32位英特尔上，乘法会影响输出的两个寄存器。 也就是说，无论您是否需要，64位都是完全可用的。 它只是编译器是否足够智能以利用它的function。

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

也就是说，在某些时候，我试图让编译器在分割结果上使用模数和除数，但1998年的旧Microsoft编译器不够智能，无法实现同样的指令产生两种结果。