How to perform rotate shift in C [duplicate]

This question already has answers here: Best practices for circular shift (rotate) operations in C++ (16 answers) Closed 5 years ago.

I have a question as described: how to perform rotate shift in C without embedded assembly. To be more concrete, how to rotate shift a 32-bit int.

I'm now solving this problem w开发者_如何学运维ith the help of type long long int, but I think it a little bit ugly and wanna know whether there is a more elegant method.

Kind regards.

---

(warning to future readers): Wikipedia's code produces sub-optimal asm (gcc includes a branch or cmov). See Best practices for circular shift (rotate) operations in C++ for efficient UB-free rotates.

---

From 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));
}

---

This answer is a duplicate of what I posted on Best-practices for compiler-friendly rotates.

See my answer on another question for the full details.

The most compiler-friendly way to express a rotate in C that avoids any Undefined Behaviour seems to be John Regehr's implementation:

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 ));
}

Works for any integer type, not just uint32_t, so you could make multiple versions. This version inlines to a single rol %cl, reg (or rol $imm8, reg) on x86, because the compiler knows that the instruction already has the mask operation built-in.

I would recommend against templating this on the operand type, because you don't want to accidentally do a rotate of the wrong width, when you had a 16bit value stored in an int temporary. Especially since integer-promotion rules can turn the result of an expression involving a narrow unsigned type into and int.

Make sure you use unsigned types for x and the return value, or else it won't be a rotate. (gcc does arithmetic right shifts, shifting in copies of the sign-bit rather than zeroes, leading to a problem when you OR the two shifted values together.)

---

Though thread is old I wanted to add my two cents to the discussion and propose my solution of the problem. Hope it's worth a look but if I'm wrong correct me please.

When I was looking for efficient and safe way to rotate I was actually surprised that there is no real solution to that. I found few relevant threads here: https://blog.regehr.org/archives/1063 (Safe, Efficient, and Portable Rotate in C/C++), Best practices for circular shift (rotate) operations in C++ and wikipedia style (which involves branching but is safe):

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

After little bit of contemplation I discovered that modulo division would fit the criteria as the resulting reminder is always lower than divisor which perfectly fits the condition of shift<32 without branching. From mathematical point of view:

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

In our case every (x % 32) < 32 which is exactly what we want to achieve. (And yes, I have checked that empirically and it always is <32)

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

Additionally mod() will simplify the process because actual rotation of, let's say 100 bits is rotating full 32 bits 3 times, which essentially changes nothing and then 4 bits. So isn't it better to calculate 100%32==4 and rotate 4 bits? It takes single processor operation anyway and brings it to rotation of constant value plus one instruction, ok two as argument has to be taken from stack, but it's still better than branching with if() like in "wikipedia" way.

So, what you guys think of that?