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

Question

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

例如,在PowerPC上,mulhw操作码在一个时钟内返回32位32位乘法的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乘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);
}