Right Rotation of Bits in C

Question

I'm working on exercise 2-8 in K&R which asks us to write function rightrot(int x, int n) such that all bits of x are shifted n times to the right with the bits that fall off the right-end reappearing on the left-end.

Here is my attempted solution in which I shift each bit one-by-one:

int rightrot(int x, int n)
{
    int i, rmb;

    for(i = 0; i < n; ++i)
    {
        // get right-most bit
        rmb = x & 1;

        // shift 1 to right
        x = x >> 1;

        // if right-most bit is set, set left-most bit
        if (rmb == 1)
            x = x | (~0 ^ (~0 >> 1) );
    }

    return x;
}

When I execute rightrot(122, 2), I expect to get 94 since 122 is 1111010 and 94 is 1011110. Instead, I get 30 which happens to be 0011110. Clearly, my method for setting the left-most bit is not working as I expect it to. Does anyone spot an obvious error? I'm just learning about capturing bits and the like.

NOTE: I got the technique for setting the left-most bit from this post.

user_3684343 · Answer

Let's analyse (~0 ^ (~0 >> 1) ):

~0 is -1
~0 >> 1 is again -1, if the sign bit is 1 rightshift will fill the new bits with 1s.
-1 ^ -1 is 0.
x = x | 0 is x.

The solution is that you should use unsigned datatypes if you want to do bitoperations.

So you should use the line x = x | (~0u ^ (~0u >> 1) );
To avoid other problems the parameter x should also be unsigned int.

https://ideone.com/7zPTQk

Right Rotation of Bits in C

1 Answers