CODEWITHSUNDEEP
c#algorithmbit-shift
Eric Bergman
Eric Bergman

Reputation: 1443

Circular Left Rotation Algorithm in C#

SO I have this algorithm that does left rotation

    public static ushort RotateLeft(ushort value, int count)
    {
        int left = value << count;
        int right = value >> (16 - count);
        return (ushort)(left | right);
    }

However this is not producing the values I want for example if I have a value of 18 when rotated left by 1 bit it the result should be 3 but instead this just adds a zero at the end:

This is what the algorithm does:

10010     18
100100    36

This is what I want:

10010     18
00101      3

The bits should be shifted out of the sign bit position (bit 0) enter the least significant bit position (bit 15) and, consequently, no bits are lost.

What I want is described here: http://www.xgc.com/manuals/m1750-ada/m1750/x2733.html

It's a CRC algorithm that I want to convert to C#

Upvotes: 1

Views: 1114

Answers (2)

Taekahn
Taekahn

Reputation: 1717

(x << n) | (x >> (<bit size> - n))

Should give you the appropriate shift, which is what your function is doing.

Upvotes: 0

Fumu 7
Fumu 7

Reputation: 1091

Your code should be corrected as follows.

I add new argument 'numberOfBits' to presents number of bits to be rotated.

public static ushort RotateLeft(ushort value, int numberOfBits int countToRotate)
{
    countToRotate = countToRotate mod numberOfBits; // in case of rotate more than once.
    ushort mask = -1  // 1s for all 16 bits.
    mask = mask << numberOfBits;

    int left = value << countToRotate;  // rotate left
    int right = left >> (numberOfBits); // move left-overflowed bits to right
    return (ushort)((left | right) & mask);
}

This code works correctly if (numOfBits+countToRotate)<=16.

Upvotes: 1

Related Questions