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.
(editor's note: Many common ways of expressing rotates in C suffer from undefined behaviour if the rotate count is zero, or compile to more than just a single rotate machine instruction. This question's answer should document best practices.)
This question is related to
c++
c
rotation
bit-manipulation
c++-faq
Definitively:
template<class T>
T ror(T x, unsigned int moves)
{
return (x >> moves) | (x << sizeof(T)*8 - moves);
}
Source Code x bit number
int x =8;
data =15; //input
unsigned char tmp;
for(int i =0;i<x;i++)
{
printf("Data & 1 %d\n",data&1);
printf("Data Shifted value %d\n",data>>1^(data&1)<<(x-1));
tmp = data>>1|(data&1)<<(x-1);
data = tmp;
}
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));
}
another suggestion
template<class T>
inline T rotl(T x, unsigned char moves){
unsigned char temp;
__asm{
mov temp, CL
mov CL, moves
rol x, CL
mov CL, temp
};
return x;
}
If x is an 8 bit value, you can use this:
x=(x>>1 | x<<7);
#define ROTATE_RIGHT(x) ( (x>>1) | (x&1?0x8000:0) )
Below is a slightly improved version of Dídac Pérez's answer, with both directions implemented, along with a demo of these functions' usages using unsigned char and unsigned long long values. Several notes:
cout << +value
trick for tersely outputting an unsigned char numerically that I found here: https://stackoverflow.com/a/28414758/1599699<put the type here>
syntax for clarity and safety.The result of a shift operation is undefined if additive-expression is negative or if additive-expression is greater than or equal to the number of bits in the (promoted) shift-expression.
Here's the code I'm using:
#include <iostream>
using namespace std;
template <typename T>
inline T rotateAndCarryLeft(T rotateMe, unsigned char shiftNum)
{
static const unsigned char TBitCount = sizeof(T) * 8U;
return (rotateMe << shiftNum) | (rotateMe >> (TBitCount - shiftNum));
}
template <typename T>
inline T rotateAndCarryRight(T rotateMe, unsigned char shiftNum)
{
static const unsigned char TBitCount = sizeof(T) * 8U;
return (rotateMe >> shiftNum) | (rotateMe << (TBitCount - shiftNum));
}
void main()
{
//00010100 == (unsigned char)20U
//00000101 == (unsigned char)5U == rotateAndCarryLeft(20U, 6U)
//01010000 == (unsigned char)80U == rotateAndCarryRight(20U, 6U)
cout << "unsigned char " << 20U << " rotated left by 6 bits == " << +rotateAndCarryLeft<unsigned char>(20U, 6U) << "\n";
cout << "unsigned char " << 20U << " rotated right by 6 bits == " << +rotateAndCarryRight<unsigned char>(20U, 6U) << "\n";
cout << "\n";
for (unsigned char shiftNum = 0U; shiftNum <= sizeof(unsigned char) * 8U; ++shiftNum)
{
cout << "unsigned char " << 21U << " rotated left by " << +shiftNum << " bit(s) == " << +rotateAndCarryLeft<unsigned char>(21U, shiftNum) << "\n";
}
cout << "\n";
for (unsigned char shiftNum = 0U; shiftNum <= sizeof(unsigned char) * 8U; ++shiftNum)
{
cout << "unsigned char " << 21U << " rotated right by " << +shiftNum << " bit(s) == " << +rotateAndCarryRight<unsigned char>(21U, shiftNum) << "\n";
}
cout << "\n";
for (unsigned char shiftNum = 0U; shiftNum <= sizeof(unsigned long long) * 8U; ++shiftNum)
{
cout << "unsigned long long " << 3457347ULL << " rotated left by " << +shiftNum << " bit(s) == " << rotateAndCarryLeft<unsigned long long>(3457347ULL, shiftNum) << "\n";
}
cout << "\n";
for (unsigned char shiftNum = 0U; shiftNum <= sizeof(unsigned long long) * 8U; ++shiftNum)
{
cout << "unsigned long long " << 3457347ULL << " rotated right by " << +shiftNum << " bit(s) == " << rotateAndCarryRight<unsigned long long>(3457347ULL, shiftNum) << "\n";
}
cout << "\n\n";
system("pause");
}
C++20 std::rotl
and std::rotr
It has arrived! http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0553r4.html and should add it to the <bit>
header.
cppreference says that the usage will be like:
#include <bit>
#include <bitset>
#include <cstdint>
#include <iostream>
int main()
{
std::uint8_t i = 0b00011101;
std::cout << "i = " << std::bitset<8>(i) << '\n';
std::cout << "rotl(i,0) = " << std::bitset<8>(std::rotl(i,0)) << '\n';
std::cout << "rotl(i,1) = " << std::bitset<8>(std::rotl(i,1)) << '\n';
std::cout << "rotl(i,4) = " << std::bitset<8>(std::rotl(i,4)) << '\n';
std::cout << "rotl(i,9) = " << std::bitset<8>(std::rotl(i,9)) << '\n';
std::cout << "rotl(i,-1) = " << std::bitset<8>(std::rotl(i,-1)) << '\n';
}
giving output:
i = 00011101
rotl(i,0) = 00011101
rotl(i,1) = 00111010
rotl(i,4) = 11010001
rotl(i,9) = 00111010
rotl(i,-1) = 10001110
I'll give it a try when support arrives to GCC, GCC 9.1.0 with g++-9 -std=c++2a
still doesn't support it.
The proposal says:
Header:
namespace std { // 25.5.5, rotating template<class T> [[nodiscard]] constexpr T rotl(T x, int s) noexcept; template<class T> [[nodiscard]] constexpr T rotr(T x, int s) noexcept;
and:
25.5.5 Rotating [bitops.rot]
In the following descriptions, let N denote
std::numeric_limits<T>::digits
.template<class T> [[nodiscard]] constexpr T rotl(T x, int s) noexcept;
Constraints: T is an unsigned integer type (3.9.1 [basic.fundamental]).
Let r be s % N.
Returns: If r is 0, x; if r is positive,
(x << r) | (x >> (N - r))
; if r is negative,rotr(x, -r)
.template<class T> [[nodiscard]] constexpr T rotr(T x, int s) noexcept;
Constraints: T is an unsigned integer type (3.9.1 [basic.fundamental]). Let r be s % N.
Returns: If r is 0, x; if r is positive,
(x >> r) | (x << (N - r))
; if r is negative,rotl(x, -r)
.
A std::popcount
was also added to count the number of 1 bits: How to count the number of set bits in a 32-bit integer?
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.
Since it's C++, use an inline function:
template <typename INT>
INT rol(INT val) {
return (val << 1) | (val >> (sizeof(INT)*CHAR_BIT-1));
}
C++11 variant:
template <typename INT>
constexpr INT rol(INT val) {
static_assert(std::is_unsigned<INT>::value,
"Rotate Left only makes sense for unsigned types");
return (val << 1) | (val >> (sizeof(INT)*CHAR_BIT-1));
}
The correct answer is following:
#define BitsCount( val ) ( sizeof( val ) * CHAR_BIT )
#define Shift( val, steps ) ( steps % BitsCount( val ) )
#define ROL( val, steps ) ( ( val << Shift( val, steps ) ) | ( val >> ( BitsCount( val ) - Shift( val, steps ) ) ) )
#define ROR( val, steps ) ( ( val >> Shift( val, steps ) ) | ( val << ( BitsCount( val ) - Shift( val, steps ) ) ) )
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,
--- Substituting RLC in 8051 C for speed --- Rotate left carry
Here is an example using RLC to update a serial 8 bit DAC msb first:
(r=DACVAL, P1.4= SDO, P1.5= SCLK)
MOV A, r
?1:
MOV B, #8
RLC A
MOV P1.4, C
CLR P1.5
SETB P1.5
DJNZ B, ?1
Here is the code in 8051 C at its fastest:
sbit ACC_7 = ACC ^ 7 ; //define this at the top to access bit 7 of ACC
ACC = r;
B = 8;
do {
P1_4 = ACC_7; // this assembles into mov c, acc.7 mov P1.4, c
ACC <<= 1;
P1_5 = 0;
P1_5 = 1;
B -- ;
} while ( B!=0 );
The keil compiler will use DJNZ when a loop is written this way.
I am cheating here by using registers ACC and B in c code.
If you cannot cheat then substitute with:
P1_4 = ( r & 128 ) ? 1 : 0 ;
r <<= 1;
This only takes a few extra instructions.
Also, changing B for a local var char n is the same.
Keil does rotate ACC left by ADD A, ACC which is the same as multiply 2.
It only takes one extra opcode i think.
Keeping code entirely in C keeps things simpler sometimes.
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. */ }
Most compilers have intrinsics for that. Visual Studio for example _rotr8, _rotr16
Source: Stackoverflow.com