按位向左旋转功能

我想实现一个向左旋转功能旋转的整数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

按位向左旋转功能

回答

相关问题