Rotate Left by x bits in C++

Question

I'm trying to write a ROL function in C++ and have seen a number of questions relating to it. My knowledge is such that I don't really understand how it works.

I am using the below code

#include<stdio.h>
#define INT_BITS 32
using namespace std;
int leftRotate(int n, unsigned d){ //rotate n by d bits
     return (n << d)|(n >> (INT_BITS - d));
}

int main() {
    int n = 0xa3519eba;
    int d = 0x0f;
    printf("Left rotation of %d by %d is ", n, d);
    printf("%d", leftRotate(n, d));
}

I'm expecting a result of 0xcf5d51a8, but instead what I get is signed 0x2e58.

Any direction on where I'm going wrong would be much appreciated.

Answer 1

Funny things happen when you try to do bit math on a signed value, because of the sign bit.

#include<stdio.h>
#define INT_BITS 32

int leftRotate(unsigned n, unsigned d){ //rotate n by d bits
     return (n << d)|(n >> (INT_BITS - d));
}

int main() {
  unsigned n = 0xa3519eba;
  unsigned d;

  for( d = 0; d < 32; d += 4 )
    printf("Left rotation of 0x%.8X by %d is 0x%.8X\n", n, d, leftRotate(n, d));
}

Output:

Left rotation of 0xA3519EBA by 0 is 0xA3519EBA
Left rotation of 0xA3519EBA by 4 is 0x3519EBAA
Left rotation of 0xA3519EBA by 8 is 0x519EBAA3
Left rotation of 0xA3519EBA by 12 is 0x19EBAA35
Left rotation of 0xA3519EBA by 16 is 0x9EBAA351
Left rotation of 0xA3519EBA by 20 is 0xEBAA3519
Left rotation of 0xA3519EBA by 24 is 0xBAA3519E
Left rotation of 0xA3519EBA by 28 is 0xAA3519EB

Answer 2

This is a very old question, but now finally the basis CPU operation of rotate (supported by instruction sets over decades) has been added to the C++ library in C++20: std::rotl. (Note: it's only implemented for the unsigned integer types, as those have defined behavior.)

You can for instance look at the implementation by Microsoft. It's hard to read, but basically says:

template <typename T>
T rotl(T val, int rotationAmount) {
    auto nrOfDigits = std::numeric_limits<T>::digits;
    auto remainder = rotationAmount % nrOfDigits;
    if (remainder > 0) {
        return static_cast<T>(
            static_cast<T>(val << remainder) | static_cast<T>(val >> (nrOfDigits - remainder)));
    } else if (remainder == 0) {
        return val; // no rotation
    } else { // _Remainder < 0
        return rotr(val, -remainder); // use rotate right
    }
}

However, you shouldn't implement this yourself. If I look at the assembly generated by GCC and Clang from the above example, they implement the code literally as described (even with -O3):

sal     esi, cl
mov     ecx, 32
mov     eax, ebx
sub     ecx, edx
shr     eax, cl
or      esi, eax

While calling std::rotl gives

rol     esi, cl

Answer 3

Make sure your numbers are the correct size in memory. This C program works (and comes with a bit-printing function to help you debug/understand).

#include <stdio.h>
#include <stdlib.h>

uint32_t print_4_bits(uint32_t x){
  int i,res;
  for(i=0;i<4;i++){
    printf("%u",(x&0x80000000)>>31);
    x=x<<1;
  }
  return x;
}

void print_bits(uint32_t x){
  int i;
  for(i=0;i<8;i++){
    x=print_4_bits(x);
    printf(" ");
  }
}

uint32_t rol32(uint32_t n, uint32_t d){
  return (n<<d)|(n>>(32-d));
}

int main(){
  uint32_t n = 0xa3519eba;
  uint32_t expected=0xcf5d51a8;
  uint32_t d = 0xf;
  print_bits(n);
  printf("\n");
  print_bits(rol32(n,d));
  printf("\n");
  if(rol32(n,d)!=expected)printf("boo\n");
}

Here is the output:

1010 0011 0101 0001 1001 1110 1011 1010 
1100 1111 0101 1101 0101 0001 1010 1000 

A bit more explanation: Each data type takes a designated amount of space in memory, and ints can be of varying sizes. Furthermore you are bit-shifting what could potentially be negative numbers stored in two's complement notation, so the shifting may be filling with 1s, as explained in this post:

Right shifting negative numbers in C

You can solve both the memory size problem and the negative numbers problem by enforcing 32-bit unsigned integers. In C (and likely C++ too) that is with uint32_t.

As for your actual bit-twiddle, say you have the number 0110 1100 and you rotate it by 2 bits, seeking 1011 0001 as a solution.

Start with

0110 1100

Shift left 2 places

1011 0000 <-right most bits filled with 0.

Shift right 8-2=6 places

0000 0001 <- left-most 6 filled with 0.

Now if you bitwise and them with | you get the bits you cared about from each part of the solution (the ones you don't care about are parenthesised).

1011 00(00) | (0000 00)01 = 1011 0001

Answer 4

It is often the case that there is some existing library function which uses a short asm{} block to execute an appropriate machine instruction. Virtually every CPU knows how to do a roll, but the operation isn't directly exposed in the "C" language. "(Shift" yes, "roll" no.)

Answer 5

Since you don't understand how what you wrote works, you have a basic problem. Don't try to short-cut the solution. Write a brute-force algorithm that rotates left one bit at a time. For each iteration of d, save each left-most bit, shift left, take each bit the falls off the left and add it on the right. Continue until you count down to 0.