Circular Shift

[BlueOctopus]

Hey everyone, I have a code written by someone else that is supposed to do a circular bitwise shift. Below I have the line of code that does that.

unsigned char x = 0x17;//in binary it is 00010111
x=(x<<1) + (x>>7) + 25;

I tried to trace the code on paper but as a result, I got "01000111", which doesn't seem like 0x17 rotated. I am a bit(unintended pun) unsure of what happens when the last bit falls off the byte. Is it moved to the first place or is it deleted? Also, I am not sure if the +25 plays any role on the bit rotation.

Any help is appreciated

[lastchance]

I'm struggling with stuff I'm not very familiar with, but here is my take for a single byte.
(And I'm definitely not sure if unsigned char is stored in 1 byte).

bits: abcdefgh

If x>>7 means shift to the right 7 times then, seemingly, it would effectively leave the single leftmost bit, which you need because its going to get knocked off when shifting everything one place to the left.
bits: 0000000a

x<<1 means shift to the left once, giving (for an unsigned representation):
bits: bcdefgh0

Then (x<<1) + (x>>7) would appear to give
bcdefgh0
+0000000a
=bcdefgha (which seems to be circularly shifted)


But I can't see why you would need +25.

[coder777]

Also, I am not sure if the +25 plays any role on the bit rotation.

Not for the bit rotation, but for the result of course.

[lastchance]

but for the result of course.

Please explain!

[JLBorges]

Assuming that CHAR_BITS == 8, x = ( x << 1U ) | ( x >> 7U ) ; would do a circular bit shift left by one.

Generalised:

// circular bit shift left of integer 'number' by 'n' bit positions
template < typename T > T circular_shift_left( T number, std::size_t n )
{
    static_assert( std::is_integral<T>::value, "an integral type is required" ) ;

    // the corresponding unsigned type if T is a signed integer, T itself otherwise
    using unsigned_type = std::make_unsigned_t<T> ;

    // number of bits in the integral type
    constexpr std::size_t NBITS = std::numeric_limits<unsigned_type>::digits ;

    n %= NBITS ; // bring the number of bit positions to shift by to within a valid range
    const unsigned_type un = number ; // the number interpreted as an unsigned value

    // circular bit shift left of an unsigned NBITS-bit integer by n bit positions
    return ( un << n ) | ( un >> (NBITS-n) ) ;
}

http://coliru.stacked-crooked.com/a/bcf698d8306b2bec

[lastchance]

Sorry, I'm thick! Still don't follow that in the context of the expression
x=(x<<1) + (x>>7) + 25;
and trying to return as an unsigned char (which is, indeed, 1 byte with my compiler/OS).

[lastchance]

Tried:

#include <iostream>
using namespace std;

int main()
{
   unsigned char x =0x17;
   cout << " Original: " << (int) x << endl;
   x = ( x << 1 ) + ( x >> 7 );                                                                                   
   cout << " Final:    " << (int) x << endl;
}

Result was:

 Original: 23
 Final:    46

23 is 00010111 in binary
46 is 00101110 in binary (shifted circularly one place)

I didn't include a '+25'

So, I plead ignorance, but I'd love to know!

[JLBorges]

See http://stackoverflow.com/a/13289498

[lastchance]

I see the code examples and I'm quite happy that their ALTERNATIVE method (using bitwise OR) works, and is probably the method of choice.

However, I still can't fathom out why the original question posed here, doing circular shift with addition, should need a '+25' at the end! It seems to work OK without (at least for unsigned char being 8 bits). Indeed it simply gives the wrong answer in my code fragment if I include it, as the original questioner pointed out.

(It was a really fascinating question, by the way, @BlueOctopus)

[BlueOctopus]

Hello again,

I would like to thank you all for answering so fast my question. To be honest I don't understand either why the +25 is there. The original algorithm is made to benchmark an Arduino, and does many useless operations, just to make the CPU work. So I suppose that this "+25" is there just to "challenge" the Arduino.

Again, thanks for the quick replies.