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?

Answer 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);
}