按位向左旋轉功能

我想實現一個向左旋轉功能旋轉的整數x n位按位向左旋轉功能

離開

例：rotateLeft（0x87654321,4）= 0x76543218
法律OPS：〜&^| + < < >>

到目前爲止，我有這樣的：

int rotateLeft(int x, int n) { 
    return ((x << n) | (x >> (32 - n))); 
}

，我已經意識到，爲簽署integers..does人不行有任何想法，如何解決這一問題？

所以現在我想：

int rotateLeft(int x, int n) { 
    return ((x << n) | ((x >> (32 + (~n + 1))) & 0x0f)); 
}

，並收到錯誤消息：

ERROR：測試rotateLeft（-2147483648 [0x80000000的]，1個[爲0x1]）失敗... ...給15 [0xf]。應該是1 [0x1]

來源

2012-04-13 asdfghjkl

想想爲什麼你的表達式不適用於帶符號整數，以及你可以對or-運算符右邊的部分做些什麼來使其有效。另外請注意，'-'不是您的合法運營商列表的一部分，所以您也需要修復。 – 2012-04-13 03:32:00

好，所以我想我想出瞭如何擺脫 - （32 +（〜n + 1）），但我很難找出我能做什麼之後|做這個工作 – asdfghjkl 2012-04-13 03:43:54

你能創建一個掩碼和多餘的1位嗎？ – 2012-04-13 03:46:14

你能定義'rotate left'爲signed int嗎？

我只需簡單地將x投射到unsigned int並按照您現在的方式執行旋轉。

另一個說明：你的代碼是否需要在不同的體系結構（不僅僅是32位）上工作？您可能想要避免對比特大小進行硬編碼。

來源

2012-04-13 03:27:05

我不能使用任何類型的轉換，我們假設整數是32位 – asdfghjkl 2012-04-13 03:28:08

你明白爲什麼你的表達式不適用於帶符號整數嗎？ – 2012-04-13 03:29:13

是因爲>>用1填充，而<<用0填充0 – asdfghjkl 2012-04-13 03:32:15

編譯器友好旋轉的當前最佳做法是this community-wiki Q&A。來自維基百科的代碼在clang或gcc超過5.1時不會產生很好的asm。

對Wikipedia有一個非常好的詳細的位置旋轉a.k.a.循環移位解釋。

從那裏報價：

unsigned int _rotl(const unsigned int value, int shift) { 
    if ((shift &= sizeof(value)*8 - 1) == 0) 
     return value; 
    return (value << shift) | (value >> (sizeof(value)*8 - shift)); 
} 

unsigned int _rotr(const unsigned int value, int shift) { 
    if ((shift &= sizeof(value)*8 - 1) == 0) 
     return value; 
    return (value >> shift) | (value << (sizeof(value)*8 - shift));

在你的情況，因爲你沒有訪問乘法運算符，你可以用<< 3取代*8。

編輯您還可以刪除if陳述，因爲您的陳述不能使用if。這是一種優化，但如果沒有它，你仍然會得到正確的價值。

請注意，如果您真的打算旋轉整數signed上的位，旋轉結果的解釋將取決於平臺。具體而言，取決於平臺是使用Two's Complement還是One's Complement。我想不出一個應用程序在哪裏旋轉有符號整數的位是有意義的。

來源

2012-04-13 03:31:55

我明白什麼是位旋轉以及它是如何工作的，但我必須用上面列出的按位運算來編程它 – asdfghjkl 2012-04-13 03:33:25

列出的實現中是否有任何您無法訪問的內容？請注意，您可以用'<< 3'替換' - 1'和'+ -1'和'* 8'。 – 2012-04-13 03:36:07

我不出聲使用sizeof或調用任何其它功能和參考，我們要承擔起我們的32個整數使用補 – asdfghjkl 2012-04-13 03:54:22

int rotateLeft(int x, int n) { 
    return (x << n) | (x >> (32 - n)) & ~((-1 >> n) << n); 
}

UPDATE：（非常感謝@George）

int rotateLeft(int x, int n) { 
    return (x << n) | (x >> (32 - n)) & ~(-1 << n); 
}

不能使用 ' - ' 版本。

int rotateLeft(int x, int n) { 
    return (x << n) | (x >> (0x1F & (32 + ~n + 1))) & ~(0xFFFFFFFF << n); 
} 

//test program 
int main(void){ 
    printf("%x\n",rotateLeft(0x87654321,4)); 
    printf("%x\n",rotateLeft(0x87654321,8)); 
    printf("%x\n",rotateLeft(0x80000000,1)); 
    printf("%x\n",rotateLeft(0x78123456,4)); 
    printf("%x\n",rotateLeft(0xFFFFFFFF,4)); 
    return 0; 
} 
/* result : GCC 4.4.3 and Microsoft(R) 32-bit C 16.00.40219.01 
76543218 
65432187 
1 
81234567 
ffffffff 
*/

來源

2012-04-13 09:43:06 BLUEPIXY

這個問題被標記爲家庭作業。讓我們避免給出明確的答案。如果他/她學習如何回答他/她自己的問題，那麼對於OP來說有更多的好處。 – 2012-04-13 14:09:32

好吧，我不會這是對的，她（他）不知道如何製作面具？ – BLUEPIXY 2012-04-13 14:22:04

我不確定你在問什麼。她不知道面具是什麼或它是如何工作的，所以她首先需要學習。無論如何，在你的回答'（-1 >> n）中'沒有效果 - 你明白爲什麼？簡單地使用〜0更好。 – 2012-04-13 14:25:09

在ISO C（不知道如果這是你實現語言或不是，但可以肯定的樣子吧）上有符號整數這是消極的，右移是實現定義的，因此應儘量避免。

無論如何，如果你正在做歪歪，你真的真的應先投入無符號整數。

來源

2013-09-17 19:46:53 mirabilos

最好的辦法是：

int rotateLeft(int x, int n) 
{ 
    _asm 
    { 
     mov eax, dword ptr [x] 
     mov ecx, dword ptr [n] 
     rol eax, cl 
    } 
}

如果需要就在你的代碼旋轉的int變量，然後最快的方法是：

#define rotl(val, shift) _asm mov eax, dword ptr[val] _asm mov ecx, dword ptr [shift] _asm rol eax, cl _asm mov dword ptr [val], eax

val是價值你旋轉，shift是旋轉的長度。

來源

2016-07-07 14:11:23 KKastaneda

這是非便攜式的，即假設內部有Intel兼容芯片。 – 2016-10-04 03:47:03

強制編譯器存儲/重新載入值和計數是一個巨大的開銷，並且比你從C獲得的編譯器識別並轉回到'rol'指令的情況差得多。 [MSVC風格的內聯asm是可怕的包裝單指令]（http://stackoverflow.com/questions/3323445/what-is-the-difference-between-asm-and-asm/35959859#35959859）。 – 2017-06-07 01:31:50

此外，如果內聯後該值也是常量，則可防止編譯時常數從優化到「rol eax，imm8」或完全優化。 – 2017-06-07 01:33:30

按位向左旋轉功能

回答

相關問題