如何在C中执行旋转移位[复制]

(警告未来的读者):维基百科的代码产生次优ASM(GCC包括分支或CMOV)。见 Best practices for circular shift (rotate) operations in C++ 为了有效的UB自由旋转。

从 Wikipedia :

unsigned int _rotl(unsigned int value, int shift) {
    if ((shift &= 31) == 0)
      return value;
    return (value << shift) | (value >> (32 - shift));
}

unsigned int _rotr(unsigned int value, int shift) {
    if ((shift &= 31) == 0)
      return value;
    return (value >> shift) | (value << (32 - shift));
}

这个答案是我发布内容的副本 Best-practices for compiler-friendly rotates .

见 my answer on another question 详细信息。

在C语言中表示旋转(避免任何未定义的行为)的编译器最友好的方法似乎是 John Regehr 的实现:

uint32_t rotl32 (uint32_t x, unsigned int n)
{
  const unsigned int mask = (CHAR_BIT*sizeof(x)-1);

  assert ( (n<=mask) &&"rotate by type width or more");
  n &= mask;  // avoid undef behaviour with NDEBUG.  0 overhead for most types / compilers
  return (x<<n) | (x>>( (-n)&mask ));
}

适用于任何整数类型,而不仅仅是 uint32_t ,这样就可以生成多个版本。本版本 inlines to a single rol %cl, reg (或) rol $imm8, reg )在x86上,因为编译器知道指令已经内置了掩码操作。

我建议不要在操作数类型上进行模板化,因为当您在 int 暂时的。尤其是整数提升规则可以将包含窄无符号类型的表达式的结果转换为和 int .

确保使用无符号类型 x 返回值,否则它不会是一个旋转。(GCC做算术右移,在符号位而不是零的副本中移动,当你 OR 两个值一起移动。)

虽然线程是旧的,但我想在讨论中加上我的两分钱,并提出我的问题解决方案。希望它值得一看,但如果我错了,请纠正我。

当我在寻找高效和安全的旋转方式时,我很惊讶没有真正的解决方案。我在这里找到了一些相关的线索: https://blog.regehr.org/archives/1063 (安全、高效、可移植的C/C++) Best practices for circular shift (rotate) operations in C++ 维基百科风格(包括分支,但安全):

uint32_t wikipedia_rotl(uint32_t value, int shift) {
    if ((shift &= 31) == 0)
      return value;
    return (value << shift) | (value >> (32 - shift));
}

经过一点思考,我发现模除符合标准,因为结果提示总是低于除数,这完全符合移位<32的条件,没有分支。 从数学的角度来看:

__x>=0,y:(x mod y)<y

在我们的例子中,每(x%32)<32,这正是我们想要实现的。(是的,我根据经验进行了检查,结果总是32分)

#include <stdint.h>
uint32_t rotl32b_i1m (uint32_t x, uint32_t shift)
    {
    shift %= 32;
    return (x<<n) | (x>>(32-shift));
    }

此外,mod()将简化该过程,因为的实际旋转,假设100位旋转了32位3次,基本上不改变任何内容,然后是4位。那么,计算100%32==4并旋转4位不是更好吗?无论如何,它需要单处理器操作,并将其转换为常量值加上一条指令,Ok2作为参数必须从堆栈中获取,但是它仍然比像“wikipedia”那样使用if()进行分支要好。

你们觉得怎么样?