按位向左旋转function
我正在尝试实现一个旋转左侧函数,它将整数x向左旋转n位
- 例如:rotateLeft(0x87654321,4)= 0x76543218
- 法律操作:〜&^ | + <>
到目前为止我有这个:
int rotateLeft(int x, int n) { return ((x <> (32 - n))); }
我已经意识到不能为签名整数工作..任何人都有任何想法如何解决这个问题?
所以现在我试过了:
int rotateLeft(int x, int n) { return ((x <> (32 + (~n + 1))) & 0x0f)); }
并收到错误:
错误:测试rotateLeft(-2147483648 [0x80000000],1 [0x1])失败…… …给出15 [0xf]。 应为1 [0x1]
编译器友好旋转的当前最佳实践是这个社区维基问答 。 来自维基百科的代码不会产生非常好的asm with clang,或gcc早于5.1。
在维基百科上有一个非常好的,详细的比特旋转解释,即循环移位。
引自那里:
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));
在您的情况下,由于您无权访问乘法运算符,因此可以将*8
替换为<< 3
。
编辑您也可以删除if
语句, if
您声明不能使用if
语句。 这是一个优化,但没有它你仍然可以获得正确的值。
请注意,如果您真的打算在有signed
整数上旋转位,则旋转结果的解释将取决于平台。 具体而言,它取决于平台是使用Two's Complement还是One's Complement 。 我想不出一个旋转有符号整数的位有意义的应用程序。
你能为signed int
定义’rotate left’吗?
我只是将x
转换为unsigned int
并按照你现在的方式执行旋转。
另请注意:您的代码是否需要在不同的体系结构(不仅仅是32位)上工作? 您可能希望避免对int
bitsize进行硬编码。
int rotateLeft(int x, int n) { return (x << n) | (x >> (32 - n)) & ~((-1 >> n) << n); }
更新:(非常感谢@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 */
在ISO C中(不知道这是否是您的实现语言,但它看起来确实如此),在带符号的整数上的shift-right是实现定义的,因此应该避免。
如果你还在做bitops,你真的应该首先转换为无符号整数。
最好的方法是:
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
是旋转的长度。