Rotate right by n only using bitwise operators in C

Question

I'm trying to implement a rotateRight by n function in C by only using bitwise operators.

So far, I have settled on using this.

y = x >> n
z = x << (32 - n)

g = y | z

So take for instance the value 11010011

If I were to try and `rotateRight(5):

y becomes 11111110

z becomes 01100000

Then g becomes 111111110

However the correct answer should be 10011110

This almost works, but the problem is that the right-shift copies the sign bit when I need it to perform logical shift, and so some of my answers are the negative of what they should be. How can I fix this?

Note I am unable to use casting or unsigned types

Answer 1

You could shift unsigned values:

y = (int)((unsigned)x >> n);
z = x << (32 - n);
g = y | z;

Or, you could mask appropriately:

y = (x >> n) & ~(-1 << (32 - n));
z = x << (32 - n);
g = y | z;

Answer 2

Though @jlahd answer is correct I will try and provide a brief explanation of the difference between a logical shift right and an arithmetic shift right (another nice diagram of the difference can be found here).

Please read the links first and then if you're still confused read below:

Brief explanation of the two different shifts right

Now, if you declare your variable as int x = 8; the C compiler knows that this number is signed and when you use a shift operator like this:

int x = 8;
int y = -8;
int shifted_x, shifted_y;

shifted_x = x >> 2; // After this operation shifted_x == 2
shifted_y = y >> 2; // After this operation shifted_y == -2

The reason for this is that a shift right represents a division by a power of 2.

Now, I'm lazy so lets make int's on my hypothetical machine 8 bits so I can save myself some writing. In binary 8 and -8 would look like this:

 8 = 00001000
-8 = 11111000 ( invert and add 1 for complement 2 representation )

But in computing the binary number 11111000 is 248 in decimal. It can only represent -8 if we remember that that variable has a sign...

If we want to keep the nice property of a shift where the shift represents a division by a power of 2 (this is really useful) and we want to now have signed numbers, we need to make two different types of right shifts because

 248 >> 1 = 124 = 01111100
 -8  >> 1 = -4  = 11111100
// And for comparison
  8  >> 1 =  4  = 00000100

We can see that the first shift inserted a 0 at the front while the second shift inserted a 1. This is because of the difference between the signed numbers and unsigned numbers, in two's complement representation, when dividing by a power of 2.

To keep this nicety we have two different right shift operators for signed and unsigned variables. In assembly you can explicitly state which you wish to use while in C the compiler decides for you based on the declared type.

Code generalisation

I would write the code a little differently in an attempt to keep myself at least a little platform agnostic.

#define ROTR(x,n) (((x) >> (n)) | ((x) << ((sizeof(x) * 8) - (n))))
#define ROTR(x,n) (((x) >> (n)) | ((x) << ((sizeof(x) * 8) - (n))))

This is a little better but you still have to remember to keep the variables unsigned when using this macro. I could try casting the macro like this:

#define ROTR(x,n) (((size_t)(x) >> (n)) | ((size_t)(x) << ((sizeof(x) * 8) - (n))))
#define ROTR(x,n) (((size_t)(x) >> (n)) | ((size_t)(x) << ((sizeof(x) * 8) - (n))))

but now I'm assuming that you're never going to try and rotate an integer larger than size_t...

In order to get rid of the upper bits of the right shift which may be 1's or 0's depending on the type of shift the compiler chooses one might try the following (which satisfies your no casting requirement):

#define ROTR(x,n) ((((x) >> (n)) & (~(0u) >> (n))) | ((x) << ((sizeof(x) * 8) - (n))))
#define ROTR(x,n) ((((x) >> (n)) & (~(0u) >> (n))) | ((x) << ((sizeof(x) * 8) - (n))))

But it would not work as expected for the long type since the ~(0u) is of type unsigned int (first type which zero fits in the table) and hence restricts us to rotations that are less than sizeof(unsigned int) * 8 bits. In which case we could use ~(0ul) but that makes it of unsigned long type and this type may be inefficient on your platform and what do we do if you want to pass in a long long? We would need it to be of the same type as x and we could achieve it by doing more magical expressions like ~((x)^(x)), but we would still need to turn it into and unsigned version so lets not go there.

@MattMcNabb also points out in the comments two more problems:

1. our left shift operation could overflow. When operating on signed types, even though in practice it is most often the same, we need to cast the x in the left shift operation to an unsigned type, because it is undefined behavior when an arithmetic shift operation overflows (see this answer's reference to the standard). But if we cast it we will once again need to pick a suitable type for the cast because its size in bytes will act as an upper limit on what we can rotate...

2. We are assuming that bytes have 8 bits. Which is not always the case, and we should use CHAR_BIT instead of 8.

In which case why bother? Why not go back to the previous solution and just use the largest integer type, uintmax_t (C99), instead of size_t. But this now means that we could be penalized in performance since we might be using integers larger than the processor word and that could involve more than just one assembly instruction per arithmetic operation... Nevertheless here it is:

#define ROTR(x,n) (((uintmax_t)(x) >> (n)) | ((uintmax_t)(x) << ((sizeof(x) * CHAR_BIT) - (n))))
#define ROTR(x,n) (((uintmax_t)(x) >> (n)) | ((uintmax_t)(x) << ((sizeof(x) * CHAR_BIT) - (n))))

So really, there is likely no perfect way to do it (at least none that I can think of). You can either have it work for all types or have it be fast by only dealing with things equal to or smaller than the processor word (eliminate long long and the likes). But this is nice and generic and should adhere to the standard...

If you want fast algorithms there is a point where you need to know what machine/s you're writing code for otherwise you can't optimize.

So in the end @jlahd's solution will work better, whilst my one might help you make things more generic (at a cost).

Answer 3

I've tried your code on x86 Linux with gcc 4.6.3.

y = x >> n
z = x << (32 - n)

g = y | z

This works correct.If x equals 11010011 then rotateRight(5) will makes y become 00000110.">>" will not add 1.