使用浮點運算對整數數據旋轉右操作？

Question

我想採用一個無符號整數表示值，並以某種方式使用浮點運算，執行向右旋轉按位旋轉操作。

看看這裏使用的巧妙：http://en.wikipedia.org/wiki/Fast_inverse_square_root 這使用了一個魔術值和一些技巧，使用整數運算對浮點數執行操作。我想要的是相反的;我正在使用的硬件針對浮點進行了大量優化，但整數運算性能較差。該算法是sha256，它大量使用旋轉右操作。

Answer 1

兩種方法浮現在腦海中：

• 以持有的整數位，他們的東西成預期將與相同的位數的浮動的變量，對這些位進行操作，就好像它們'是一個浮動。希望硬件有一些浮點操作，這些操作在SHA256使用的整數操作方式相同的方式上操作。
• 將您的整數填充到具有更多位的浮點變量中（例如，將Int32放入Double中，可以保持53位而不會丟失精度），然後使用數學運算實現向右旋轉操作。

第一個選項不太可能奏效。如果您的硬件基於IEEE 754浮點標準（最常見的浮點表示標準），則浮點數將存儲爲位域;例如，double有一個符號位，11個指數位和53個小數位。不會有任何操作將符號位的值轉換爲指數位插槽之一。然後有一些位模式具有特殊的含義，並且貫穿整個操作的意義，如NaN和無窮。所以這個想法可能是一個不起眼的東西。

我不相信第二種方法也可以;你需要完全控制四捨五入等行爲，並希望說服自己在浮點值中有適當數量的位，並且你絕對需要大量測試來證明自己正在獲得全系列投入的預期產出。但是在這裏。

一個向右旋轉的操作 - 比如x ror y - 因此發生故障。設b是x中的位數。我假設一切都使用無符號算術完成，因爲它使邏輯更簡單。

• 我們從x ror y開始。
• 這可以表示爲右移，左移和OR，如(x shr y) or (x shl (b - y))。
• Shr與2的冪相除。 Shr會丟棄掉下端的任何位，所以我們可以使用floor函數來模擬它。所以現在我們有floor(x/2^y) or (x shl (b - y))。
• Shl與乘以2的冪相同。 Shl丟棄掉上端的任何位，我們可以通過乘以2^b模來模擬。這給了我們floor(x/2^y) or ((x * 2^(b - y)) mod 2^b)。
• 由於shl和shr的結果是不相交的（它們影響結果中的不同位），所以或者可以用加法完成。所以現在我們有整個旋轉操作的數學符號：floor(x/2^y) + ((x * 2^(b - y)) mod 2^b)。

現在只需在每個地方插入該公式SHA256執行旋轉右移操作，並查看它是否比整數算術更快。似乎不太可能，但並非不可能 - 即使整數硬件沒有快速移位，添加兩個具有不同指數的浮點數也需要FP硬件內的快速移位操作。