8

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 and unsigned int 24,( 11000), and it had to give the output unsigned 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.

Improve this question
10
  • So your value is 4 bits wide? The code you have shown works for a value of type unsigned int, which is much more than 4 bits. Commented Sep 12, 2014 at 1:10
  • your function is correct. An integer has 32 bits, not 4. Commented Sep 12, 2014 at 1:10
  • @GregHewgill You are talking about "classical rotating shift", but OP asks for a different thing. It could be misunderstanding what "circular shift" means. Commented Sep 12, 2014 at 1:11
  • what's your definition for CHAR_BIT, I　test it with 8 ,it outputs 24 Commented Sep 12, 2014 at 1:13
  • The function looks OK and implements circular shift (as it is commonly understood). I.e. if you shift a number by 1, bit 31 goes to position 0, regardless of its value. What you are expecting and illustrating in your sample, is something totally different. Commented Sep 12, 2014 at 1:21

6 Answers 6

Reset to default
6

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 :)

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

forgot "#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
6

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.

Improve this answer

Comments

0

It's because you're using an int which is 32 bits, so it worked as expected by wrapping the most significant bits to the front. Use a smaller data structure like an unsigned char to make this more managable.

Improve this answer

Comments

0

You have more than 4 bits in your integer, most likely 32, but could theoretically be 64 or 16. So your bits for the value 12 are 00000000000000000000000000001100. Doing a left rotation by 1 would naturally give you the value 00000000000000000000000000011000 (=24).

Improve this answer

Comments

0

if you want bitwise rotation over an arbitrary number of bits (for example 4), simply add a parameter to your function:

unsigned int rotl(unsigned int value, int shift, unsigned int width) {
    return ((value << shift) & (UINT_MAX >> (sizeof(int) * CHAR_BIT - width))) | (value >> (width - shift));
}
Improve this answer

3 Comments

You also need to mask the answer to the proper number of bits. And I think your formula is slightly off too.
The * CHAR_BIT is wrong here, assuming that width is in bits, not bytes. You mean: return ((1U << width) - 1) & ((value << shift) | (value >> (width - shift)));.
The if test should be if (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.
0

If you don't use C++20, you may want to have two helper functions like:

template< std::size_t N >
[[ nodiscard ]] std::bitset< N > rotl( std::bitset< N > b, std::size_t const n ) noexcept
{
    return b << n | b >> ( N - n );
}

template< std::size_t N >
[[ nodiscard ]] std::bitset< N > rotr( std::bitset< N > b, std::size_t const n ) noexcept
{
    return b >> n | b << ( N - n );
}

and use them the same as you would use C++20's std::rotl and std::rotr.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.