Circular shifting in C, unexpected behavior

Question

I'm currently doing an exercise from The C Programming Language (K&R) [exercise 2.8] to write a right circular shift function to rotate an integer x, n places.

I believe I have come up with a solution, but for some strange reason, when I shift beyond the word length, (ie. a 100 place shift), I am still getting the correct answer when I believe I shouldn't with the code below.

#include <stdio.h>

unsigned rightrot(unsigned x, int n);

int main(void)
{
    printf("%u\n", rightrot(1,100));  /* this should yield zero (overshift) */
    return 0;
}

unsigned rightrot(unsigned int x, int n)
{
    unsigned a = ~0;
    int i;

    for (i = 1; a > 1; ++i)     /* calculating the word length */
        a = a/2;

    return (x >> n) | (x << (i-n));
}

The shifts on the line:

return (x >> n) | (x << (i-n));

should shift all of the binary digits out at leave 0 | 0 I would have thought, when passed a shift size larger than the word length. But to my surprise this code returns exactly the same answers as if I was to use the following version that allows for n larger than the word length:

return (x >> (n % i)) | (x << ((i-n) % i);

remembering that i is the word length.

I am using gcc 4.7.2 with -std=c89 and -pedantic-errors, and get no warnings either.

Answer 1

Shifting by more than the wordsize in C in UNDEFINED, so anything might happen. On most machines, shifts are done with a mux-tree with log₂wordsize select bits, disregarding the higher bits of the shift count, so a shift of 100 on a 32-bit machine is likely to be the same as a shift of 4. But you might get anything, including a crash.

Answer 2

If n is greater than i, then i - n is negative. Using the << operator with a negative number as the right operand is undefined behavior.