How do I perform a circular rotation of a byte?

Manuel picture Manuel · Oct 6, 2013 · Viewed 16.3k times · Source

I'm trying to implement a function that performs a circular rotation of a byte to the left and to the right.

I wrote the same code for both operations. For example, if you are rotating left 1010 becomes 0101. Is this right?

unsigned char rotl(unsigned char c) {
    int w;
    unsigned char s = c;
    for (w = 7; w >= 0; w--) {
       int b = (int)getBit(c, w);//
       if (b == 0) {
           s = clearBit(s, 7 - w);
       } else if (b == 1) {
           s = setBit(s, 7 - w);
       }
    }
    return s;
}

unsigned char getBit(unsigned char c, int n) {
    return c = (c & (1 << n)) >> n;
}

unsigned char setBit(unsigned char c, int n) {
    return c = c | (1 << n);
}

unsigned char clearBit(unsigned char c, int n) {
    return c = c &(~(1 << n));
}

Answer

mkf picture mkf · Oct 6, 2013

There is no rotation operator in C, but if you write:

unsigned char rotl(unsigned char c)
{
    return (c << 1) | (c >> 7);
}

then, according to this: http://www.linux-kongress.org/2009/slides/compiler_survey_felix_von_leitner.pdf (page 56), compilers will figure out what you want to do and perform the rotation it in only one (very fast) instruction.