Best practices for circular shift (rotate) operations in C++

Question

Left and right shift operators (<< and >>) are already available in C++. However, I couldn't find out how I could perform circular shift or rotate operations.

How can operations like "Rotate Left" and "Rotate Right" be performed?

Rotating right twice here

Initial --> 1000 0011 0100 0010

should result in:

Final   --> 1010 0000 1101 0000

An example would be helpful.

(editor's note: Many common ways of expressing rotates in C suffer from undefined behaviour if the rotate count is zero, or compile to more than just a single rotate machine instruction. This question's answer should document best practices.)

Solution 1

See also an earlier version of this answer on another rotate question with some more details about what asm gcc/clang produce for x86.

The most compiler-friendly way to express a rotate in C and C++ that avoids any Undefined Behaviour seems to be John Regehr's implementation. I've adapted it to rotate by the width of the type (using fixed-width types like uint32_t).

#include <stdint.h>   // for uint32_t
#include <limits.h>   // for CHAR_BIT
// #define NDEBUG
#include <assert.h>

static inline uint32_t rotl32 (uint32_t n, unsigned int c)
{
  const unsigned int mask = (CHAR_BIT*sizeof(n) - 1);  // assumes width is a power of 2.

  // assert ( (c<=mask) &&"rotate by type width or more");
  c &= mask;
  return (n<<c) | (n>>( (-c)&mask ));
}

static inline uint32_t rotr32 (uint32_t n, unsigned int c)
{
  const unsigned int mask = (CHAR_BIT*sizeof(n) - 1);

  // assert ( (c<=mask) &&"rotate by type width or more");
  c &= mask;
  return (n>>c) | (n<<( (-c)&mask ));
}

Works for any unsigned integer type, not just uint32_t, so you could make versions for other sizes.

See also a C++11 template version with lots of safety checks (including a static_assert that the type width is a power of 2), which isn't the case on some 24-bit DSPs or 36-bit mainframes, for example.

I'd recommend only using the template as a back-end for wrappers with names that include the rotate width explicitly. Integer-promotion rules mean that rotl_template(u16 & 0x11UL, 7) would do a 32 or 64-bit rotate, not 16 (depending on the width of unsigned long). Even uint16_t & uint16_t is promoted to signed int by C++'s integer-promotion rules, except on platforms where int is no wider than uint16_t.

---

On x86, this version inlines to a single rol r32, cl (or rol r32, imm8) with compilers that grok it, because the compiler knows that x86 rotate and shift instructions mask the shift-count the same way the C source does.

Compiler support for this UB-avoiding idiom on x86, for uint32_t x and unsigned int n for variable-count shifts:

• clang: recognized for variable-count rotates since clang3.5, multiple shifts+or insns before that.
• gcc: recognized for variable-count rotates since gcc4.9, multiple shifts+or insns before that. gcc5 and later optimize away the branch and mask in the wikipedia version, too, using just a ror or rol instruction for variable counts.
• icc: supported for variable-count rotates since ICC13 or earlier. Constant-count rotates use shld edi,edi,7 which is slower and takes more bytes than rol edi,7 on some CPUs (especially AMD, but also some Intel), when BMI2 isn't available for rorx eax,edi,25 to save a MOV.
• MSVC: x86-64 CL19: Only recognized for constant-count rotates. (The wikipedia idiom is recognized, but the branch and AND aren't optimized away). Use the _rotl / _rotr intrinsics from <intrin.h> on x86 (including x86-64).

gcc for ARM uses an and r1, r1, #31 for variable-count rotates, but still does the actual rotate with a single instruction: ror r0, r0, r1. So gcc doesn't realize that rotate-counts are inherently modular. As the ARM docs say, "ROR with shift length, n, more than 32 is the same as ROR with shift length n-32". I think gcc gets confused here because left/right shifts on ARM saturate the count, so a shift by 32 or more will clear the register. (Unlike x86, where shifts mask the count the same as rotates). It probably decides it needs an AND instruction before recognizing the rotate idiom, because of how non-circular shifts work on that target.

Current x86 compilers still use an extra instruction to mask a variable count for 8 and 16-bit rotates, probably for the same reason they don't avoid the AND on ARM. This is a missed optimization, because performance doesn't depend on the rotate count on any x86-64 CPU. (Masking of counts was introduced with 286 for performance reasons because it handled shifts iteratively, not with constant-latency like modern CPUs.)

BTW, prefer rotate-right for variable-count rotates, to avoid making the compiler do 32-n to implement a left rotate on architectures like ARM and MIPS that only provide a rotate-right. (This optimizes away with compile-time-constant counts.)

Fun fact: ARM doesn't really have dedicated shift/rotate instructions, it's just MOV with the source operand going through the barrel-shifter in ROR mode: mov r0, r0, ror r1. So a rotate can fold into a register-source operand for an EOR instruction or something.

---

Make sure you use unsigned types for n and the return value, or else it won't be a rotate. (gcc for x86 targets 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. Right-shifts of negative signed integers is implementation-defined behaviour in C.)

Also, make sure the shift count is an unsigned type, because (-n)&31 with a signed type could be one's complement or sign/magnitude, and not the same as the modular 2^n you get with unsigned or two's complement. (See comments on Regehr's blog post). unsigned int does well on every compiler I've looked at, for every width of x. Some other types actually defeat the idiom-recognition for some compilers, so don't just use the same type as x.

---

Some compilers provide intrinsics for rotates, which is far better than inline-asm if the portable version doesn't generate good code on the compiler you're targeting. There aren't cross-platform intrinsics for any compilers that I know of. These are some of the x86 options:

• Intel documents that <immintrin.h> provides _rotl and _rotl64 intrinsics, and same for right shift. MSVC requires <intrin.h>, while gcc require <x86intrin.h>. An #ifdef takes care of gcc vs. icc. Clang 9.0 also has it, but before that it doesn't seem to provide them anywhere, except in MSVC compatibility mode with -fms-extensions -fms-compatibility -fms-compatibility-version=17.00. And the asm it emits for them sucks (extra masking and a CMOV).
• MSVC: _rotr8 and _rotr16.
• gcc and icc (not clang): <x86intrin.h> also provides __rolb/__rorb for 8-bit rotate left/right, __rolw/__rorw (16-bit), __rold/__rord (32-bit), __rolq/__rorq (64-bit, only defined for 64-bit targets). For narrow rotates, the implementation uses __builtin_ia32_rolhi or ...qi, but the 32 and 64-bit rotates are defined using shift/or (with no protection against UB, because the code in ia32intrin.h only has to work on gcc for x86). GNU C appears not to have any cross-platform __builtin_rotate functions the way it does for __builtin_popcount (which expands to whatever's optimal on the target platform, even if it's not a single instruction). Most of the time you get good code from idiom-recognition.

// For real use, probably use a rotate intrinsic for MSVC, or this idiom for other compilers.  This pattern of #ifdefs may be helpful
#if defined(__x86_64__) || defined(__i386__)

#ifdef _MSC_VER
#include <intrin.h>
#else
#include <x86intrin.h>  // Not just <immintrin.h> for compilers other than icc
#endif

uint32_t rotl32_x86_intrinsic(rotwidth_t x, unsigned n) {
  //return __builtin_ia32_rorhi(x, 7);  // 16-bit rotate, GNU C
  return _rotl(x, n);  // gcc, icc, msvc.  Intel-defined.
  //return __rold(x, n);  // gcc, icc.
  // can't find anything for clang
}
#endif

Presumably some non-x86 compilers have intrinsics, too, but let's not expand this community-wiki answer to include them all. (Maybe do that in the existing answer about intrinsics).

---

(The old version of this answer suggested MSVC-specific inline asm (which only works for 32bit x86 code), or http://www.devx.com/tips/Tip/14043 for a C version. The comments are replying to that.)

Inline asm defeats many optimizations, especially MSVC-style because it forces inputs to be stored/reloaded. A carefully-written GNU C inline-asm rotate would allow the count to be an immediate operand for compile-time-constant shift counts, but it still couldn't optimize away entirely if the value to be shifted is also a compile-time constant after inlining. https://gcc.gnu.org/wiki/DontUseInlineAsm.

Solution 2

C++20 std::rotl and std::rotr

It has arrived! http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0553r4.html and should add it to the <bit> header.

cppreference says that the usage will be like:

#include <bit>
#include <bitset>
#include <cstdint>
#include <iostream>

int main()
{
    std::uint8_t i = 0b00011101;
    std::cout << "i          = " << std::bitset<8>(i) << '\n';
    std::cout << "rotl(i,0)  = " << std::bitset<8>(std::rotl(i,0)) << '\n';
    std::cout << "rotl(i,1)  = " << std::bitset<8>(std::rotl(i,1)) << '\n';
    std::cout << "rotl(i,4)  = " << std::bitset<8>(std::rotl(i,4)) << '\n';
    std::cout << "rotl(i,9)  = " << std::bitset<8>(std::rotl(i,9)) << '\n';
    std::cout << "rotl(i,-1) = " << std::bitset<8>(std::rotl(i,-1)) << '\n';
}

giving output:

i          = 00011101
rotl(i,0)  = 00011101
rotl(i,1)  = 00111010
rotl(i,4)  = 11010001
rotl(i,9)  = 00111010
rotl(i,-1) = 10001110

I'll give it a try when support arrives to GCC, GCC 9.1.0 with g++-9 -std=c++2a still doesn't support it.

The proposal says:

Header:

namespace std {
  // 25.5.5, rotating   
  template<class T>
    [[nodiscard]] constexpr T rotl(T x, int s) noexcept;
  template<class T>
    [[nodiscard]] constexpr T rotr(T x, int s) noexcept;

and:

25.5.5 Rotating [bitops.rot]

In the following descriptions, let N denote std::numeric_limits<T>::digits.

template<class T>
  [[nodiscard]] constexpr T rotl(T x, int s) noexcept;

Constraints: T is an unsigned integer type (3.9.1 [basic.fundamental]).

Let r be s % N.

Returns: If r is 0, x; if r is positive, (x << r) | (x >> (N - r)); if r is negative, rotr(x, -r).

template<class T>
  [[nodiscard]] constexpr T rotr(T x, int s) noexcept;

Constraints: T is an unsigned integer type (3.9.1 [basic.fundamental]). Let r be s % N.

Returns: If r is 0, x; if r is positive, (x >> r) | (x << (N - r)); if r is negative, rotl(x, -r).

A std::popcount was also added to count the number of 1 bits: How to count the number of set bits in a 32-bit integer?

Solution 3

Since it's C++, use an inline function:

template <typename INT> 
INT rol(INT val) {
    return (val << 1) | (val >> (sizeof(INT)*CHAR_BIT-1));
}

C++11 variant:

template <typename INT> 
constexpr INT rol(INT val) {
    static_assert(std::is_unsigned<INT>::value,
                  "Rotate Left only makes sense for unsigned types");
    return (val << 1) | (val >> (sizeof(INT)*CHAR_BIT-1));
}

Solution 4

Most compilers have intrinsics for that. Visual Studio for example _rotr8, _rotr16

Solution 5

Definitively:

template<class T>
T ror(T x, unsigned int moves)
{
  return (x >> moves) | (x << sizeof(T)*8 - moves);
}

View more solutions

Comments

[jww]

Possible duplicate of Near constant time rotate that does not violate the standards

[Ciro Santilli OurBigBook.com]

It has arrived in C++20! stackoverflow.com/a/57285854/895245

[Rich]

you should wrap x into parentheses to avoid nasty surprises with expressions as argument to the macro.

[James Hopkin]

If the value's not 16-bit, you silently get nonsense

[unwind]

Is this really a rotate left? And isn't the part with the sizeof missing an &, or something?

[S M Kamran]

Similar to the subroutines above... b = b << m | b >> (N-m);

[MSalters]

Fixed the roation direction, and this assumes you're shifting in zeroes on both sides (which is why you shouldn't do this for signed integer types).

[H. Green]

Need to modify it to account for shifts greater than the length of the bitset.

[Phil Miller]

If defining it as a macro, one then also need to be careful to avoid passing an expression with side effects as the argument.

[B.K.]

Shouldn't that be XOR, not OR? 1 ^ 0 = 1, 0 ^ 0 = 0, etc. If it's OR it's not exclusive, thus it'll always be 1.

[Nobody moving away from SE]

Warning: This code is broken if INT is a signed integer and the sign is set! Test for example rol<std::int32_t>(1 << 31) which should flip over to 1 but actually becomes -1 (because the sign is retained).

[Nobody moving away from SE]

See ideone.com/aRait7 for a live example of this behavior and the suggested solution (casting the type to the equivalent unsigned type before shifting).

[MSalters]

@Nobody: I already commented 5 years ago that you shouldn't use signed integer types. Rotation doesn't make sense on signed integer types anyway.

[Nobody moving away from SE]

@MSalters: Sorry for the noise. Maybe you should edit that into the answer instead of burying it in the comments. (I wonder how it slipped by my notice, I thought I had read all comments before writing). Anyways the function itself does not warn about problems and even a seasoned programmer might oversee that he/she is passing a signed integer. The very least should be a compile-time check that the passed type is an unsigned integer.

[Milania]

Added m %= N; to account for shifts >= N.

[mirabilos]

Curious, why not bits = CHAR_BIT * sizeof(n); and c &= bits - 1; and return ((n >> c) | (n << (bits - c))), which is what I’d use?

[Fake Name]

It's probably worth noting that INT appears to be a defined type in MSVC++, so the C++11 version won't work on windows unless you change that to something else.

[Fake Name]

Also, vs is missing constexpr. Sigh.

[Peter Cordes]

@mirabilos: Your version has UB with bits=32, count=32, in the shift by bits - c = 32 - 0. (I didn't get a ping from this because I only edited the wiki, not writing it in the first place.)

[mirabilos]

@PeterCordes 0 < count < bits is a constant requirement of almost all CPUs and programming languages implementing rotation (sometimes 0 ≤ count < bits, but shifting by the exact amount of bits is virtually always either not defined or rounds down to a nop instead of clearing the value, and rotating, well.)

[Peter Cordes]

@mirabilos: Right, but our goal is to write a function that feeds the shift count directly to a single asm instruction, but avoids UB on a C level for any possible shift count. Since C doesn't have a rotate operator or function, we want to avoid UB in any of the component parts of this idiom. We'd rather not rely on the compiler treating a C shift the same way as asm shift instructions on the target its compiling for. (And BTW, ARM does zero the register with variable-count shifts by more than the register width, taking the count from the bottom byte of the register. Link in the answer.)

[Peter Cordes]

@mirabilos: The common compilers work fine with your idiom, IIRC, but they would be allowed to make demons fly out of your nose if they wanted to with a count of 0 producing x << 32. C really does say that's undefined behaviour, not just an implementation-defined result value or something.

[Peter Cordes]

You can use std::numeric_limits<INT>::digits instead of CHAR_BIT * sizeof. I forget if unsigned types are allowed to have unused padding (e.g. 24-bit integers stored in 32 bits), but if so then digits would be better. See also gist.github.com/pabigot/7550454 for a version with more check for a variable-count shift.

[mirabilos]

@PeterCordes hm sure, but then just disallow that value. (Nevermind, I got your point and your answer, thanks for the verbose explanation.)

[MSalters]

@PeterCordes: They are. I think Cray's did (used floating point registers with padding where exponent field would be).

[BeeOnRope]

I was going to say "just use portable-snippets" but then I checked the code and it seems to (a) invoke UB for zero shift counts and (b) only use intrinsics on MSVC. In general though having that as the compilable "reference code" for what works with all the compiler-and-platform specific hacks seems like a nice idea...

[Toby Speight]

The best template version of this I ever wrote starts with template <typename T, int width = sizeof T * CHAR_BIT>. But then you no longer get to assume that width is an exact power of 2.

[Andry]

In time critical code is better to use intrinsics, the short precompiled version of well known functions. It's definitely does not slow down the overall performance. When custom implementation CAN slow down even with the __forceinline modificator.

[Toby Speight]

Is that 8 a misspelling of CHAR_BIT (which need not be exactly 8)?

[sam hocevar]

Will probably misbehave if x is signed.

[sam hocevar]

Will probably misbehave if val is signed.

[Slava]

@fake-name '> so the C++11 version won't work on windows unless you change that to something else...' Yeah, change that to linux. :)

[MSalters]

Since this is the same answer as mine (except swapping right for left), Peter Cordes' comment on my answer also applies here: use std::numeric_limits<T>::digits.

[Trass3r]

"assuming that uint32_t is exactly 32 bits wide, although C/C++ only guarantees that it's at least that wide." Where did you read that? Those typedefs are optional (didn't know that) if not supported by the hardware but they are guaranteed to be exactly the given size: en.cppreference.com/w/c/types/integer

[Gabe Halsmer]

wow! way easier then the accepted answer. btw, for a DWORD (32-bit) use _rotr and _rotl.

[Peter Cordes]

@Trass3r: IDK what I was thinking when I originally wrote that about uint32_t. I fixed it a while ago, only noticed your comment now. (Unfortunately this CW answer wasn't originally posted by me so I didn't get notified. However I am "following" it now so I'll get notified in future.)

[sandthorn]

How come bit rotations took so long to land in modern c++? Even in LLVM clang, there just have been intrinsics just a few years ago => reviews.llvm.org/D21457 I thought ARM had had rotate way before 2010, so they should have been there since c++11.

[spectras]

An answer that uses macros for this task simply cannot be considered correct.

[Peter Cordes]

@sandthorn: I think the C++ and C committees have a very optimistic view of the idea that compilers should be able to recognize portable idioms (like (x >> r) | (x << (N-r))) and compile them to rotate instructions, so the base language doesn't need to include popcount or rotate. Of course given that attitude, IDK why they include a * multiply operator for integers when you could just write shift-and-add loops everywhere. It seems like C++20 was how long it took for someone to finally talk some sense into them and add stuff that most CPUs have, like popcnt and bit-scan; easily emulated.