How do you rotate bits left and right?
Short answer: Combine two shifts with OR: rotate left is (x << n) | (x >> (32 - n)). Mask the shift amounts with & 31 so that n = 0 does not produce a shift by 32, which is undefined.
#include <stdint.h>
static inline uint32_t rotl32(uint32_t x, unsigned n)
{
n &= 31;
return (x << n) | (x >> ((32 - n) & 31));
}
static inline uint32_t rotr32(uint32_t x, unsigned n)
{
n &= 31;
return (x >> n) | (x << ((32 - n) & 31));
}
Rotate vs shift: a shift throws away the bits that fall off one end and fills with zeros. A rotate puts the bits that fall off one end back in at the other end, so no information is lost.
x = 0x80000001
x << 1 = 0x00000002 (top bit lost)
rotl(x, 1) = 0x00000003 (top bit wrapped to bit 0)
Why the & 31: for n = 0, the naive x >> (32 - 0) is a shift by 32, which is undefined in C. On Arm the LSR by 32 gives 0, but on x86 the shift count is masked to 5 bits and gives x. Undefined behaviour means the optimiser may assume it never happens.
The compiler recognises this pattern and emits one instruction: ROR on Arm (there is no rotate-left; it uses ROR by 32 - n), ROL/ROR on x86. C23 adds stdc_rotate_left/stdc_rotate_right to <stdbit.h>.
Uses: hash functions and CRC/crypto (SHA-256, ChaCha20 are built from rotates), circular LED patterns, and rotating a bitmap of round-robin slots.
Rotate other widths: for a uint8_t, use 7 and 8 instead of 31 and 32, and cast the result back to uint8_t, because the operands are promoted to int before shifting.