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.

Please provide an [mre] and explain your understanding of the `^` operator and the concept of how you use it in your program. — Yunnosch, Jan 02 '21 at 16:18
@Yunnosch Are you referring to the fact that I didn't include explicitly include my main method? I'm new to SO so I'm genuinely not sure. — awinston, Jan 02 '21 at 17:18
My understanding of the ^ operator is that it sets a bit to 1 if only one of the operands has that bit set to 1, but otherwise it sets that bit to 0. — awinston, Jan 02 '21 at 17:20
I mistakenly thought that ~0 >> 1 would result in 0111111, but @mch below explained that it would actually be 1111111 since I'm using signed data types, so that seems to be the main source of my error. — awinston, Jan 02 '21 at 17:24

mch · Accepted Answer · 2021-01-03T11:23:37.713

7

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

edited Jan 03 '21 at 11:23

answered Jan 02 '21 at 16:21

mch

9,424
2
28
42

2

*`~0 >> 1` is again `-1`,* Note that is [implementation-defined](https://port70.net/~nsz/c/c11/n1570.html#6.5.7p5). – Andrew Henle Jan 02 '21 at 16:29
even you answer speaks about *unsigned* probably better to (also) indicate `(~0u ^ (~0u >> 1))` directly in your answer to not have to follow the link. Also integrate the remark of @AndrewHenle in your answer – bruno Jan 02 '21 at 16:36
Thanks for typing out that example! When I updated my data types to unsigned int, my result ends up being 2147483678, and I see that is the same result that you got in your example. I was still expecting the result to be 94. Is there something else that I'm missing? – awinston Jan 02 '21 at 17:16
1

@awinston This is because you are using `int` with a compiler that uses 32 bit integers. If you look at the binary form of 2147483678, you will see that the topmost bit is actually set, as you expect. You are assuming 7 bit integers... – the busybee Jan 02 '21 at 17:42
@thebusybee Wow, not sure why I assumed I was working with 7 bit ints. Thanks! – awinston Jan 02 '21 at 17:44

Right Rotation of Bits in C

1 Answers1