Rotate bits

Overview

A rotation is a shift that wraps: bits pushed off one end reappear at the other, so no information is lost. Built from primitives it is (x << n) | (x >> (32 - n)) for a left rotate. That expression contains a trap that catches almost everyone — when n is 0, the second half becomes x >> 32, and shifting by the full width of the type is undefined behaviour. The fix is two lines: mask the rotation amount with n &= 31 so it is always in range, then return x unchanged when n is 0. Rotation is not a C operator; you assemble it yourself, which is precisely why the edge case is yours to handle.

Why it matters

Rotations are the structural backbone of cryptographic hash functions and ciphers — SHA-256, MD5, ChaCha20 and AES all rotate constantly, because rotation mixes bits without losing any. They also appear in hash-table hashing and checksum routines. And the n == 0 bug is genuinely dangerous: it is undefined behaviour that often appears to work on one compiler and produces garbage on another or at a different optimisation level.

Core concepts

Rotate versus shift. A shift discards the bits that fall off the end and feeds in zeros; a rotate wraps them around. Rotation is therefore reversible — rotating left by n and then right by n restores the original.

The construction. Left rotate: the part that stays is x << n; the part that wraps is x >> (32 - n). OR them together. Right rotate mirrors it: (x >> n) | (x << (32 - n)).

Normalise the amount. n &= 31 maps any rotation amount into 0..31, which is correct because rotating by 32 is the identity. This also defuses negative or oversized inputs.

Guard n == 0. After masking, n may be 0, and x >> (32 - 0) is x >> 32 — undefined. Return x immediately in that case. Masking alone is not sufficient; both steps are required.

Width discipline. The 32 in the expression must match the type exactly. Rotating a uint64_t with 32 in the formula silently produces wrong results; use 63/64 or derive from sizeof.

Syntax notes

#include <stdint.h>

uint32_t rotl32(uint32_t x, int n) {
    n &= 31;                              // normalise into 0..31
    if (n == 0) return x;                 // MUST guard: x >> 32 is undefined
    return (x << n) | (x >> (32 - n));
}

uint32_t rotr32(uint32_t x, int n) {
    n &= 31;
    if (n == 0) return x;
    return (x >> n) | (x << (32 - n));
}

Key points:

• Both the mask and the zero guard are required; neither alone is enough.
• Use uint32_t, not int — the wrap-around relies on unsigned semantics.
• The literal 32 must match the type's width; parameterise it if you write a 64-bit version.

Lesson

A rotation shifts bits and wraps the ones that fall off back in the other end: rotl(x,n) = (x<<n) | (x>>(32-n)). The subtlety is n==0 — x >> 32 is undefined, so reduce n mod 32 and special-case zero.

The demo rotates a value both ways and shows they invert.

Code examples

#include <stdio.h>
#include <stdint.h>
static uint32_t rotl32(uint32_t x,int n){ n&=31; if(!n) return x; return (x<<n)|(x>>(32-n)); }
static uint32_t rotr32(uint32_t x,int n){ n&=31; if(!n) return x; return (x>>n)|(x<<(32-n)); }
int main(void){
    uint32_t x = 0x12345678u;
    printf("rotl 8 : 0x%08X\n", rotl32(x,8));
    printf("rotr 8 : 0x%08X\n", rotr32(x,8));
    printf("rotl then rotr = 0x%08X\n", rotr32(rotl32(x,13),13));
    return 0;
}

Line by line

Common mistakes

A 32-bit shift when n is 0 or a multiple of 32 (undefined behaviour).

Debugging tips

Compiler errors and warnings:

• warning: right shift count >= width of type — you evaluated x >> 32; the zero guard is missing.
• -Wshift-count-overflow for a constant rotation of 32; normalise with &= 31.

Runtime symptoms:

• Rotating by 0 returns garbage (or works only in debug builds). The undefined x >> 32 — the signature bug of this lesson. On x86 the CPU masks the shift count to 5 bits so it often "works"; on other targets or at -O2 it does not.
• Bits are lost rather than wrapped. You used a plain shift, or the two halves use mismatched widths.
• A negative amount misbehaves. n &= 31 handles it; without the mask, a negative shift count is undefined.
• A 64-bit rotate is wrong. The formula still says 32. Match the width to the type.

Technique: test n = 0, n = 32 and n = 1 first — those three catch essentially every implementation bug. Then assert rotr(rotl(x, n), n) == x.

Memory safety

This lesson is fundamentally about an undefined-behaviour hazard, so the safety notes are the lesson:

• Shifting by the type's width is undefined. Not zero, not the identity — undefined. Compilers exploit this; code that works today can break at a higher optimisation level. The n == 0 guard is mandatory.
• Normalise untrusted amounts. A rotation amount from input must be masked (n &= 31) before it reaches any shift. Never shift by an unvalidated value.
• Signed types break the wrap. >> on a signed negative value sign-extends, corrupting the wrapped-in bits. Use uint32_t/uint64_t.
• Width mismatch is silent. Nothing warns when a 64-bit value is rotated with a 32 in the formula; derive the width from the type when you can.

Real-world uses

Concrete uses: SHA-1, SHA-256, MD5, BLAKE2 and ChaCha20 all use fixed rotations as their diffusion primitive. AES's key schedule rotates words. MurmurHash and xxHash rotate while mixing. Some CPUs expose a rotate instruction directly, and compilers recognise the masked-and-guarded idiom above and emit it.

Professional best practices:

Beginner:

• Write the mask and the guard together, every time — treat them as one unit.
• Always use fixed-width unsigned types.

Intermediate:

• Prefer a well-tested rotl32/rotr32 helper over open-coding rotations at each site; one correct implementation beats twenty chances to forget the guard.
• In cryptographic code, keep rotation amounts constant where the algorithm specifies them — variable rotations can leak timing information on some hardware.
• If you write a 64-bit variant, parameterise the width rather than copying and editing the 32-bit one.

Practice tasks

1. (Beginner) Implement rotl32/rotr32. Include both the n &= 31 mask and the n == 0 guard. Example: rotl32(0x12345678, 8) → 0x34567812. Concepts: rotation construction, undefined shifts.

2. (Beginner) Test the edges. Verify n = 0, n = 32 and n = 33 all behave (0 and 32 are the identity; 33 equals a rotate by 1). Concepts: normalisation, edge cases.

3. (Intermediate) Round-trip property. Assert rotr32(rotl32(x, n), n) == x for random x and n in 0..63. Concepts: reversibility, property testing.

4. (Intermediate) 64-bit rotate. Write uint64_t rotl64(uint64_t x, int n) with n &= 63 and the matching guard. Requirements: must not reuse the literal 32. Concepts: width discipline.

Summary

A rotation wraps rather than discards: (x << n) | (x >> (32 - n)) for a left rotate, mirrored for a right one. Two guards make it correct — n &= 31 normalises any amount into range, and an explicit n == 0 early return avoids x >> 32, which is undefined behaviour rather than a harmless no-op. Use fixed-width unsigned types so the wrapped bits are not sign-extended, keep the width literal matched to the type, and test n = 0, 32 and 1 first because those three cases catch nearly every mistake.

Practice with these exercises

• Rotate left
• Rotate right