K&R C Exercise 2-8: rightrot — Rotate Bits Right

K&R C Exercise 2-8 — rightrot(x, n)

Exercise 2-8: Write a function rightrot(x,n) that returns the value of the integer x rotated to the right by n bit positions.

Approach

A right rotation is different from a right shift. When you shift right by n, the n bits that fall off the right end are lost and zeros fill in from the left. When you rotate right by n, those same bits that exit on the right reappear on the left. No bits are lost.

The formula combines a right shift with a left shift of the complement amount:

result = (x >> n) | (x << (wordlen - n));

The right shift moves most bits into their new positions. The left shift takes the n bits that were shifted off the right end and places them at the top of the word. ORing the two halves gives the rotated value.

Three important details:

1. Use unsigned so that >> is a logical shift (fills with zeros), not an arithmetic shift (fills with sign bits). The K&R exercise specifies an integer, but rotation only makes sense with a fixed-width unsigned value.
2. Determine word length portably at runtime using a counting loop rather than hard-coding 32. This keeps the code correct on 16-bit, 32-bit, and 64-bit platforms.
3. Guard with n % wordlen to handle the case where the caller passes n >= wordlen. Left-shifting by the word width or more is undefined behaviour in C.

Portable word-length detection

static int wordlength(void)
{
    int i;
    unsigned v = ~0U;         /* all bits set */
    for (i = 0; v != 0; ++i)
        v >>= 1;              /* shift out one bit at a time */
    return i;
}

Starting from all-ones and shifting right until the value reaches zero counts exactly how many bits are in an unsigned int on the current platform. No <limits.h> needed.

Worked example (32-bit system)

x = 0x000000F0 = 0000 0000 0000 0000 0000 0000 1111 0000
n = 4,  wordlen = 32

x >> 4        = 0000 0000 0000 0000 0000 0000 0000 1111 = 0x0000000F
x << 28       = 1111 0000 0000 0000 0000 0000 0000 0000 = 0xF0000000

result        = 0xF000000F

The four low bits of 0xF0 (which are 0000) wrap around to the top; the four high bits of 0xF0 (1111) shift down by 4. The result is 0xF000000F.

C Source Code

/* K&R Exercise 2-8 — rightrot
 * Compile: gcc -ansi -Wall ex2-8.c -o ex2-8 */
#include <stdio.h>

unsigned rightrot(unsigned x, int n);

static int wordlength(void)
{
    int i;
    unsigned v = ~0U;
    for (i = 0; v != 0; ++i)
        v >>= 1;
    return i;
}

unsigned rightrot(unsigned x, int n)
{
    int wlen = wordlength();
    n = n % wlen;
    if (n == 0)
        return x;
    return (x >> n) | (x << (wlen - n));
}

int main(void)
{
    printf("wordlength = %d bits\n", wordlength());
    printf("rightrot(0xF0, 4)  = 0x%08X\n", rightrot(0xF0, 4));
    printf("rightrot(0x01, 1)  = 0x%08X\n", rightrot(0x01, 1));
    printf("rightrot(0xFF, 8)  = 0x%08X\n", rightrot(0xFF, 8));
    return 0;
}

Compile and Run

gcc -ansi -Wall ex2-8.c -o ex2-8 && ./ex2-8

Sample Output

wordlength = 32 bits
rightrot(0xF0, 4)  = 0xF000000F
rightrot(0x01, 1)  = 0x80000000
rightrot(0xFF, 8)  = 0xFF000000

The second call rotates the lone set bit in 0x01 one position to the right: it exits the right end and reappears at bit 31, giving 0x80000000. The third call rotates 0xFF right by a full byte (8 positions): the eight low bits wrap around to positions 31–24, giving 0xFF000000.

What This Exercise Teaches

• Rotation vs. shift — a rotation is an information-preserving transformation; no bits are destroyed. Rotations appear in cryptographic algorithms (AES, SHA, Salsa20) where every bit must eventually influence every other bit.
• Portable word-length detection — counting bits with a loop avoids hardcoded constants and works without <limits.h>. It’s the style K&R favours in the exercises surrounding this one.
• n % wordlen guard — left-shifting an unsigned int by its own width or more is undefined behaviour in C. The modulus prevents that without a branch in the common case.
• Unsigned right shift — declaring x as unsigned ensures >> is a logical shift. Arithmetic right shift on a signed value would fill the vacated positions with the sign bit, corrupting the rotation.
• Combining two shifts with OR — the trick of splitting a rotation into (x >> n) | (x << (w-n)) is recognised by modern compilers (GCC, Clang) and compiled directly to a single native ROR or RCR instruction.

Set Up Your C Environment

You can compile and run this code on any system with GCC. If you haven’t set up C yet for Chapter 2:

• Install GCC on Windows
• Install GCC on macOS
• Install GCC on Linux
• VS Code for C Programming — recommended editor with integrated terminal

Book: The C Programming Language, 2nd Ed — Kernighan & Ritchie

---

← Exercise 2-7
 | 
Chapter 2 Solutions
 | 
Exercise 2-9 →