CODEWITHSUNDEEP
carraysrotationbit-manipulationunsigned
Subzero
Subzero

Reputation: 961

Understanding unsigned char left rotation in C

I needed to do a left rotate of an unsigned char array by 1 using C. I found the folowing code on the internet that I am having a hard time to fathom. I never thought it would be so complicated (at least it is, for me). Can someone please help me understand exactly what's going on with the code here?

/* accept an unsigned char array, with size and rotate it left by one 1 position*/

static void rotate_left( unsigned char * input, int size)
{
    int i, carry_back= 0;

    if(input[size-1] & (1<<(CHAR_BIT - 1)))
    {
        carry_back = 1;
    }

    for(i= size-1; i>=0; i--)
    {
        unsigned char carry = 0;

        if(i!= 0 && (input[i-1] & (1<<(CHAR_BIT - 1))))
        {
            carry = 1;
        }
        input[i] <<= 1;
        input[i] |= carry;

    }

    if(carry_back == 1)
    {
        input[0] |= 0x01;
    }

}

Upvotes: 2

Views: 266

Answers (1)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 727047

This code rotates left by one bit a sequence of size size of unsigned chars, represented by input pointer. The sequence is arranged back-to-front, as in little endian systems.

In order to do that you start from the back of the sequence, and work your way left, each time extracting the most significant bit to shift, or "carry", into the prior unsigned char. The extraction of the most significant bit is done using this formula: input[i] & (1<<(CHAR_BIT - 1)) which amounts to checking the bit by "masking" it using bitwise & operator. Each individual unsigned char is also shifted left, with its most significant bit dropped.

As the final step the algorithm pushes the most significant bit of the last unsigned char, as represented by carry_back, into the least significant bit of the initial unsigned char, thus completing the rotation.

Why are we checking input[i-1] in i!=0 && (input[i-1] & (1<<CHAR_BIT -1)))?

Because the sequence is arranged in such a way that the next unsigned char to the left of position i is located at position i+1, so i-1 is actually to the right of position i.

why are we doing an OR between input[i] and the carry at the end?

We do it to complete the rotation, making the shift circular.

Upvotes: 1

Related Questions