Bitwise rotation (circular shift)
Solution 1
Following code works great
#include <cstdint>
std::uint32_t rotl(std::uint32_t v, std::int32_t shift) {
std::int32_t s = shift>=0? shift%32 : -((-shift)%32);
return (v<<s) | (v>>(32-s));
}
std::uint32_t rotr(std::uint32_t v, std::int32_t shift) {
std::int32_t s = shift>=0? shift%32 : -((-shift)%32);
return (v>>s) | (v<<(32-s));
}
and of course the test for it.
#include <iostream>
int main(){
using namespace std;
cout<<rotr(8,1)<<endl; // 4
cout<<rotr(8,-1)<<endl; //16
cout<<rotl(8,1)<<endl; //16
cout<<rotl(8,-1)<<endl; //4
cout<<rotr(4,60)<<endl; //64
cout<<rotr(4,61)<<endl; //32
cout<<rotl(4,3)<<endl; //32
cout<<rotl(4,4)<<endl; //64
return 0;
}
maybe I not provided the fastest implementation, but a portable and stable one for sure
Generic version
#include <cstdint>
template< class T>
inline T rotl( T v, std::int32_t shift){
std::size_t m = sizeof(v)*std::numeric_limits<T>::digits;
T s = shift>=0? shift%m: -((-shift)%m)
return (v<<s) | (v>>(m-s));
}
template< class T>
inline T rotr( T v, std::int32_t shift){
std::size_t m = sizeof(v)*std::numeric_limits<T>::digits;
T s = shift>=0? shift%m: -((-shift)%m)
return (v>>s) | (v<<(m-s));
}
Cheers :)
Solution 2
C++20 provides std::rotl
and std::rotr
in the <bit>
header. An example from cppreference.com:
#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';
}
I believe std::bitset
is only used in this example for its stream formatting.
user3721105
Updated on June 13, 2022Comments
-
user3721105 almost 2 years
I was trying to make some code in C++ about “bitwise rotation” and I would like to make this by the left shif. I didn’t know how to code this, but I found a little code in “Wikipedia” like this.
unsigned int rotl(unsigned int value, int shift) { return (value << shift) | (value >> (sizeof(value) * CHAR_BIT - shift)); }
Then I tried to make it work, but this code don’t give the output that I expected. Ex. I have the number
unsigned int 12
, in binary 1100, and when I want to do bitwise rotation by the left shif with the code above, the output is andunsigned int 24
,( 11000), and it had to give the outputunsigned int 9
, because if I make the bitwise rotation(left shif), the first MSB bit have to be now the first bit, and all the others bits have to move one bit to left.Can you help to understand what is the problem of that ?, or if I am doing something wrong.
Thank you.
-
Mark Ransom over 9 yearsYou also need to mask the answer to the proper number of bits. And I think your formula is slightly off too.
-
Carlo Wood over 9 yearsThe
* CHAR_BIT
is wrong here, assuming thatwidth
is in bits, not bytes. You mean:return ((1U << width) - 1) & ((value << shift) | (value >> (width - shift)));
. -
Carlo Wood over 9 yearsThe
if
test should beif (width > sizeof(value) * CHAR_BIT)
, but it seems that that is implied. No need to add that branch there, it would make this a lot slower than needed. -
CoffeDeveloper over 9 yearsforgot "#include <limits>" and have to remove "sizeof(v)" in the generic version of code (was using CHAR_BITS). Free points for any editer. I can hardly figure a faster version without using assembly instructions