乘法的高位比特的有效計算

許多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庫解決（這是過度殺傷，將有巨大的開銷）。

上證所似乎有PMULHUW，這是一個16x16-> 16位版本，但不是32x32-> 32位版本，就像我正在尋找。

2009-09-08 SPWorley

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); 
}

2009-09-09 00:17:36 caf

是，幾乎所有的每個編譯我使用過將在-O2上執行此操作，如果不在-O1上。 – 2009-09-09 02:34:01

我不認爲有一種方法在標準的C/C++做這++比你已經有了更好。我要做的是寫一個簡單的程序集封裝器，它返回你想要的結果。

並不是說你在問Windows，但作爲一個例子，儘管Windows有一個聽起來像你想要的API（一個32乘32位乘以獲得完整的64位結果），它實現了乘以一個宏，做你在做什麼：

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

2009-09-09 00:05:24

在32位英特爾，乘法會影響輸出的兩個寄存器。也就是說，無論您是否需要，64位都是完全可用的。它只是編譯器是否足夠聰明以利用它的功能。

現代編譯器做令人驚奇的事情，所以我的建議是一些更具有優化標誌進行實驗，至少在英特爾。你會認爲優化器可能知道處理器從32乘32位產生一個64位的值。

這就是說，在某些時候，我試圖讓編譯器使用模數以及除法結果上的紅利，但1998年的舊微軟編譯器不夠聰明，無法實現同樣的指令產生兩種結果。

2009-09-09 00:06:09

回答