Circular shift operations in C++

Question

Left and right shift operators (<< and >>) are already available in C++. However, I couldn't find out how I could perform circular shift or rotate operations.

How can operations like "Rotate Left" and "Rotate Right" be performed?

Rotating right twice here

Initial --> 1000 0011 0100 0010

should result in:

Final   --> 1010 0000 1101 0000

An example would be helpful.

Answer 1

#define ROTATE_RIGHT(x) ( (x>>1) | (x&1?0x8000:0) )

Answer 2

using the inline assembler:

__asm
{
rol number,1
}

Clarification: rol, ror are the bitshift operators of the cpu. the one represents the amount. You can use normal variable names in the inline assemler.

Addit: Here's a page with solutions in C

Answer 3

Since it's C++, use an inline function:

template <typename INT> 
T rol(T val) {
    return (val << 1) | (val >> (sizeof(T)*CHAR_BIT-1));
}

C++0x would add constexpr as the return expression is an ICE if the argument is.

Answer 4

Assuming you want to shift right by L bits, and the input x is a number with N bits:

unsigned ror(unsigned x, int L, int N) 
{
    unsigned lsbs = x & ((1 << L) - 1);
    return (x >> L) | (lsbs << (N-L));
}

Answer 5

Overload a function:

unsigned int rotate_right(unsigned int x)
{
 return (x>>1 | (x&1?0x80000000:0))
}

unsigned short rotate_right(unsigned short x) { /* etc. */ }

Answer 6

Most compilers have intrinsics for that. Visual Studio for example _rotr8, _rotr16

Answer 7

How abt something like this, using the standard bitset ...

#include <bitset> 
#include <iostream> 

template <std::size_t N> 
inline void 
rotate(std::bitset<N>& b, unsigned m) 
{ 
   b = b << m | b >> (N-m); 
} 

int main() 
{ 
   std::bitset<8> b(15); 
   std::cout << b << '\n'; 
   rotate(b, 2); 
   std::cout << b << '\n'; 

   return 0;
}

HTH,

Answer 8

In details you can apply the following logic.

If Bit Pattern is 33602 in Integer

1000 0011 0100 0010

and you need to Roll over with 2 right shifs then: first make a copy of bit pattern and then left shift it: Length - RightShift i.e. length is 16 right shift value is 2 16 - 2 = 14

After 14 times left shifting you get.

1000 0000 0000 0000

Now right shift the value 33602, 2 times as required. You get

0010 0000 1101 0000

Now take an OR between 14 time left shifted value and 2 times right shifted value.

1000 0000 0000 0000
0010 0000 1101 0000
===================
1010 0000 1101 0000
===================

And you get your shifted rollover value. Remember bit wise operations are faster and this don't even required any loop.

Answer 9

or you can use this: if x is 8bit:

x=(x>>1 | x<<7);