C: binary leftrotate

1.1k views Asked by At

I wrote this little code in C:

int leftrotate (int x, int offset)
{
    return ( x << offset ) | ( x >> (32 - offset));
}

I'm expecting to binary leftrotate an integer, meaning I'm expecting to move all the bits from the given offset to the left and boucling if the number is too big.

For example, when I input :

10100110100110100101000011111101 = 2795131133 = a69a50fd

I'm expecting as return :

01101001101001010000111111011010 = 1772425178 = 69a50fda

(notice that the hexadecimal a at the begining is now at the end because I choose offset 4 in this particular example)

But instead, I got:

11111111111111111111111111111010 = 4294967290 = fffffffa
  • Any ideas where it can come from or what I'm doing wrong ?
  • Am I using the correct int? should I use uint instead ? Or maybe char ?
  • Does it depends of the architecture of my computer (32 bits or 64 bits) ?
  • I guess it depends of the length of the integer (that's why I'm using a 32 bits length number) ?

Thanks !!!

1

There are 1 answers

0
Carl Norum On BEST ANSWER

It's implementation defined whether a right shift is an arithmetic or a logical shift. In your case, it appears to be an arithmetic shift, so you're getting sign extension in the >> half of your expression. You need to put an unsigned cast or assignment in to get the behaviour you want.

unsigned int y = x;
return ( y << offset ) | ( y >> (32 - offset));

Any ideas where it can come from or what I'm doing wrong ?

Sign-extension due to right shifting a signed value.

Am I using the correct int? should I use uint instead ? Or maybe char ?

Changing to unsigned int in your function signature might be the easiest, yes.

Does it depends of the architecture of my computer (32 bits or 64 bits) ?

No, probably not.

I guess it depends of the length of the integer (that's why I'm using a 32 bits length number) ?

No, probably not. You could make your program not depend on the size of the integer, though:

return (y << offset) | (y >> ((sizeof y * CHAR_BIT) - offset));