Rotate right using bit operation in c

Question

I am trying to come up with a function int rotateRight (int x, int n) that rotates x to the right by n. For example,

rotateRight(0x87654321,4) = 0x76543218

This is what I have so far:

int rotateRight(int x, int n) {
  int mask = (((1 << n)-1)<<(32-n));
  int reserve = (int)((unsigned) (x&mask) >>(32-n));
  return (x << n) | reserve; 
}

However, I am forbidden to use any casting, and the allowed operations are ~ & ^ | + << and >>. Can anyone help me fix this?

Solution 1

Basically all you have to do is:

• shift everything right by n bits using right shift: >>

• shift the bits you want to rotate all the way to the left: <<

• Combine the shifted right and shifted left bits with or: |

See this code for an example implementation using the function signature you require:

int rotateRight(int x, int n) {

    //if n=4, x=0x12345678:

    //shifted = 0x12345678 >> 4 = 0x01234567
    int shifted = x >> n;

    //rot_bits = (0x12345678 << 28) = 0x80000000
    int rot_bits = x << (32-n);

    //combined = 0x80000000 | 0x01234567 = 0x81234567
    int combined = shifted | rot_bits;

    return combined;
}

This implementation isn't safe though, at least not without a few guarantees - namely that x will always be positive, and n will be positive and always <= 32.

If you pass in a negative integer for shifting, it will work incorrectly since it will sign-extend the left-most bit. If you want this function to work for all integers, you should change all the types from int to unsigned int (that way no sign-extension or negative left-shifting will take place) and then modulo n by 32 (% 32). Here is a safe version of the function:

unsigned int rotateRight(unsigned int x, unsigned int n) {

    //needed so you don't right shift more than int width
    n %= 32;

    //needed so you don't left shift more than int width
    unsigned int leftshift_val = (32-n) % 32 

    unsigned int shifted = x >> n;
    unsigned int rot_bits = x << leftshift_val;
    unsigned int combined = shifted | rot_bits;

    return combined;
}

And golfed down to a single line, for you minimalists:

unsigned rotr(unsigned x, unsigned n) {
    return (x >> n % 32) | (x << (32-n) % 32);
}

Solution 2

A rotation is done with a combination of left and right shifts.

Shifting a signed integer's sign bit is a problem. Suggest converting to unsigned to perform the shift. @The Paramagnetic Croissant

An example of implementation-defined behavior is the propagation of the high-order bit when a signed integer is shifted right.

Shifting by the bit width or more is a problem. Limit actual shifting to n modulo Bit_width. OP's (...<<(32-n)); code is a problem when n == 0.

OP's example looks more like a left rotate. Will assume the function should rotate right. (0x87654321,4) --> 0x18765432. @Mark Shevchenko

An int may have a width other than 32.

---

#include <limits.h>
#define INT_BIT_WIDTH (sizeof (int) * CHAR_BIT)

int rotateRight(int x, int n) {
  unsigned xu = x;
  unsigned nu = n;
  nu %= INT_BIT_WIDTH;
  unsigned y = xu >> nu;
  if (nu > 0) {
    y |= xu << (INT_BIT_WIDTH - nu);
  }
  return y;
}

---

[Edit] as OP is limited to ~ & ^ | + << >>, use the alternate following code.
Note: This is an issue in rare cases where the width of an int is not a power of 2.

// nu %= INT_BIT_WIDTH;
nu &= INT_BIT_WIDTH - 1;

[Edit2] Thought I would form an unsigned minimalistic solution as inspired by @RPGillespie as OP cannot use %.

#include <limits.h>
#define UNS_WIDTH    (sizeof (unsigned) * CHAR_BIT)
#define UNS_WIDTH_M1 (UNS_WIDTH - 1)

unsigned unsigned_rotate_right(unsigned x, unsigned n) {
  return (x >> (n & UNS_WIDTH_M1)) | (x << ((UNS_WIDTH - n) & UNS_WIDTH_M1));
}

Comments

[jim mcnamara]

Forbidden to use something usually implies a homework question. Were you given examples of something similar (like rotate the other direction)?

[Mark Shevchenko]

Looks like rotate left. :)

[paupau]

Is this what u mean ex. rotateRight(0x87654321,4) = 0x76543218 and rotateRight(0x87654321,8) = 0x65432187? I figured out how to perform such task but i dont know how to do it without casting.

[The Paramagnetic Croissant]

"I am forbidden to use any casting" – but why would you need any sort of casting for this at all? Just make the arguments and temporaries unsigned and you're good to go.

[chux - Reinstate Monica]

Detail about %32 - should code attempt that to fix things: some_int%32 is not a modulo that returns 0-31. It is the C remainder operand that return -31 to 31 in this case. some_int%32u will achieve a "safe" reduction for all int encodings.

[mch]

it should be unsigned int n, otherwise an overflowing leftshift will result in undefined behaviour.

[Iwillnotexist Idonotexist]

@mch That's not even the biggest problem! That's almost an academic concern compared to the fact that right-shifting n will sign-extend n if it's negative on 2's complement machines (which is to say, the vast majority of them)!

[Iwillnotexist Idonotexist]

Can you please change your code to use n &= 31;, unsigned x and unsigned shifted, rot_bits, combined;? At present both answers to this code are dangerously wrong (esp. with that signed right-shift) and that's holding me back from upvoting.

[Gillespie]

@IwillnotexistIdonotexist OP asked for a function with the signature int (int, int) so that's what I provided. I mention the dangers associated with the code underneath the code itself as well as how to fix it, but I will append a safe version of the code to the end of my answer.

[chux - Reinstate Monica]

x << (32-n) fails when n==0. Shifting the bit width or more is undefined. Could use x << ((32-n)%32) although that looks ugly.

[Iwillnotexist Idonotexist]

Touché; But it is still possible to have the external interface specified by the OP, provided that there are internal assignments (apparently, casts are forbidden) to unsigned. Something a la int ror(int x, unsigned n){n&=31;unsigned ux = x;return n ? (ux >> n)|(ux << (32-n)) : ux;}.

[WhozCraig]

Sign extension of the MSB on right-shift isn't the only caveat in the int version of this. If x << (32-n) shifts a bit in to, or beyond the MSB of the signed type, the resulting expression is UB, well-before it is handed off to the final | operator. (§6.5.7/4).

[Gillespie]

@chux Fair point, I added that extra precaution and then golfed it down.

[Iwillnotexist Idonotexist]

I notice OP cannot use - either, so under the light assumption that we're using a 2's complement machine, replace - n with + (~n+1). I don't object to the other minuses since they are compile-time evaluable.

[Jonathan Komar]

//needed so you don't right shift more than int width///needed so you don't left shift more than int width: that is good info! I was getting hung up on that silly detail when it is just a safety measure to ensure a proper input domain! Probably needs an if(n>0) around your modulo operations to handle n==0 as @chux mentioned, and an if(n==0) {combined = x};.

[Gillespie]

@JonathanKomar Note that the size of the integer depends on the compiler. Instead of a hardcoded modulo 32, you should check sizeof(int) on your compiler