Bitwise rotate left function

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]

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.

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

UPDATE:(thanks a lot @George)

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

not use '-' version.

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

//test program
int main(void){
    printf("%x\n",rotateLeft(0x87654321,4));
    printf("%x\n",rotateLeft(0x87654321,8));
    printf("%x\n",rotateLeft(0x80000000,1));
    printf("%x\n",rotateLeft(0x78123456,4));
    printf("%x\n",rotateLeft(0xFFFFFFFF,4));
    return 0;
}
/* result : GCC 4.4.3 and Microsoft(R) 32-bit C 16.00.40219.01
76543218
65432187
1
81234567
ffffffff
*/

The best way is:

int rotateLeft(int x, int n)
{
    _asm
    {
        mov eax, dword ptr [x]
        mov ecx, dword ptr [n]
        rol eax, cl
    }
}

If you need to rotate an int variable right in your code, then the fastest way is:

#define rotl( val, shift ) _asm mov eax, dword ptr[val] _asm mov ecx, dword ptr [shift] _asm rol eax, cl _asm mov dword ptr [val], eax

val is the value you rotate, shift is the length of the rotation.

Bitwise rotate left function

Related

Recent Posts