按位向左旋转功能

Question

我正在尝试实现一个旋转左侧函数,它将整数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]

Answer 1

编译器友好旋转的当前最佳实践是这个社区维基问答.来自维基百科的代码不会产生非常好的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.这是一个优化,但没有它你仍然可以获得正确的值.

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

Answer 2

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
*/

Answer 3

你能为 a 定义“向左旋转”吗signed int？

我会简单地转换x为 anunsigned int并按照您现在的方式执行旋转。

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