c - Bitwise rotate left function

Question

I am trying to implement a rotate left function that rotates an integer x left by n bits

• Ex: rotateLeft(0x87654321,4) = 0x76543218
• Legal ops: ~ & ^ | + << >>

so far I have this:

int rotateLeft(int x, int n) {
  return ((x << n) | (x >> (32 - n)));
}

which I have realized to not work for signed integers..does anyone have any ideas as how to fix this?

so now I tried:

int rotateLeft(int x, int n) {
  return ((x << n) | ((x >> (32 + (~n + 1))) & 0x0f));
}

and receive the error:

ERROR: Test rotateLeft(-2147483648[0x80000000],1[0x1]) failed... ...Gives 15[0xf]. Should be 1[0x1]

Answer 1

Current best practice for compiler-friendly rotates is this community-wiki Q&A. The code from wikipedia doesn't produce very good asm with clang, or gcc older than 5.1.

There's a very good, detailed explanation of bit rotation a.k.a. circular shift on Wikipedia.

Quoting from there:

unsigned int _rotl(const unsigned int value, int shift) {
    if ((shift &= sizeof(value)*8 - 1) == 0)
      return value;
    return (value << shift) | (value >> (sizeof(value)*8 - shift));
}

unsigned int _rotr(const unsigned int value, int shift) {
    if ((shift &= sizeof(value)*8 - 1) == 0)
      return value;
    return (value >> shift) | (value << (sizeof(value)*8 - shift));

In your case, since you don't have access to the multiplication operator, you can replace *8 with << 3.

EDIT You can also remove the if statements given your statement that you cannot use if. That is an optimization, but you still get the correct value without it.

Note that, if you really intend to rotate bits on a signed integer, the interpretation of the rotated result will be platform dependent. Specifically, it will depend on whether the platform uses Two's Complement or One's Complement. I can't think of an application where it is meaningful to rotate the bits of a signed integer.