11

我正在尝试实现一个左旋转函数，它将整数 x 左旋转 n 位

  • 例如：rotateLeft(0x87654321,4) = 0x76543218
  • 法律行动：~ & ^ | + << >>

到目前为止，我有这个：

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

我已经意识到不适用于有符号整数..有没有人知道如何解决这个问题？

所以现在我尝试了：

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

并收到错误：

错误：测试 rotateLeft(-2147483648[0x80000000],1[0x1]) 失败... ...给出 15[0xf]。应该是 1[0x1]

4

6 回答 6

16

当前编译器友好旋转的最佳实践是这个 community-wiki Q&A。来自 wikipedia 的代码不会产生非常好的带有 clang 的 asm，或者 gcc 早于 5.1。

Wikipedia上有关于位旋转又名循环移位的非常好的详细解释。

从那里引用：

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。这是一种优化，但没有它你仍然可以获得正确的值。

请注意，如果您真的打算在signed整数上旋转位，则旋转结果的解释将取决于平台。具体来说，这将取决于平台使用的是Two's Complement还是One's Complement。我想不出一个有意义的应用程序来旋转有符号整数的位。

于 2012-04-13T03:31:55.133 回答
4 
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
*/
于 2012-04-13T09:43:06.317 回答
1

最好的方法是：

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-07T14:11:23.333 回答
0

您可以为 a 定义“向左旋转”signed int吗？

我会简单地投射x到一个unsigned int并按照你现在拥有的方式执行旋转。

另一方面：您的代码是否需要在不同的架构（不仅仅是 32 位）上工作？您可能希望避免对位大小进行硬编码int。

于 2012-04-13T03:27:05.073 回答
0

在 ISO C 中（不知道这是否是您的实现语言，但它确实看起来像），负数的有符号整数的右移是实现定义的，因此应该避免。

如果你无论如何都在做 bitops，你真的应该首先转换为无符号整数。

于 2013-09-17T19:46:53.140 回答
0

我找到了一种进行旋转的方法，当您使用一些尺寸固定并且您知道它的位时，它会很有用：

int rotate_bit_left(int bit_rotating){
 int LastMax = 64;
 bit_rotating = (bit_rotating>=LastMax)? ((bit_rotating << 1 ) | 0x01) : bit_rotating << 1 ;
 return bit_rotating;
 /*
  Here LastMax is 64 because in the exemple I work in the Ascii table where the max is 0111 1111 and this value can be adapted with the value of the last one bit in decimale
 */
}

这个功能可以改成右旋转

int rotate_bit_right(int bit_rotating){
 bit_rotating = ((bit_rotating%2)==1)? ((bit_rotating >> 1)| 0x80 ): bit_rotating >> 1 ;
 return bit_rotating; 
 /*
 Because if is a odd number then the last bit is one and we have to put it in the first place
 */
}

请注意，如果您在除 Ascii 表之外的其他情况下使用以下模式工作，则必须更改 0x01 和 0x80：0...0001 用于左旋转 100....0 用于右旋转

于 2020-02-12T17:17:15.083 回答