How do I perform a circular rotation of a byte?

Question

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));
}

Solution 1

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.

Solution 2

Reading the answers and comments so far, there seems to be some confusion about what you are trying to accomplish - this may be because of the words you use. In bit manipulation, there are several "standard" things you can do. I will summarize some of these to help clarify different concepts. In all that follows, I will use abcdefgh to denote 8 bits (could be ones or zeros) - and as they move around, the same letter will refer to the same bit (maybe in a different position); if a bit becomes "definitely 0 or 1, I will denote it as such).

1) Bit shifting: This is essentially a "fast multiply or divide by a power of 2". The symbol used is << for "left shift" (multiply) or >> for right shift (divide). Thus

abcdefgh >> 2 = 00abcdef

(equivalent to "divide by four") and

abcdefgh << 3 = abcdefgh000 

(equivalent to "multiply by eight" - and assuming there was "space" to shift the abc into; otherwise this might result in an overflow)

2) Bit masking: sometimes you want to set certain bits to zero. You do this by doing an AND operation with a number that has ones where you want to preserve a bit, and zeros where you want to clear a bit.

abcdefgh & 01011010 = 0b0de0g0

Or if you want to make sure certain bits are one, you use the OR operation:

abcdefgh | 01011010 = a1c11f1h

3) Circular shift: this is a bit trickier - there are instances where you want to "move bits around", with the ones that "fall off at one end" re-appearing at the other end. There is no symbol for this in C, and no "quick instruction" (although most processors have a built-in instruction which assembler code can take advantage of for FFT calculations and such). If you want to do a "left circular shift" by three positions:

circshift(abcdefgh, 3) = defghabc

(note: there is no circshift function in the standard C libraries, although it exists in other languages - e.g. Matlab). By the same token a "right shift" would be

circshift(abcdefgh, -2) = ghabcdef

4) Bit reversal: Sometimes you need to reverse the bits in a number. When reversing the bits, there is no "left" or "right" - reversed is reversed:

reverse(abcdefgh) = hgfedcba

Again, there isn't actually a "reverse" function in standard C libraries.

Now, let's take a look at some tricks for implementing these last two functions (circshift and reverse) in C. There are entire websites devoted to "clever ways to manipulate bits" - see for example this excellent one. for a wonderful collection of "bit hacks", although some of these may be a little advanced...

unsigned char circshift(unsigned char x, int n) {
  return (x << n) | (x >> (8 - n));
}

This uses two tricks from the above: shifting bits, and using the OR operation to set bits to specific values. Let's look at how it works, for n = 3 (note - I am ignoring bits above the 8th bit since the return type of the function is unsigned char):

(abcdefgh << 3)       = defgh000
(abcdefgh >> (8 - 3)) = 00000abc

Taking the bitwise OR of these two gives

defgh000 | 00000abc = defghabc

Which is exactly the result we wanted. Note also that a << n is the same as a >> (-n); in other words, right shifting by a negative number is the same as left shifting by a positive number, and vice versa.

Now let's look at the reverse function. There are "fast ways" and "slow ways" to do this. Your code above gave a "very slow" way - let me show you a "very fast" way, assuming that your compiler allows the use of 64 bit (long long) integers.

unsigned char reverse(unsigned char b) {
  return (b * 0x0202020202ULL & 0x010884422010ULL) % 1023;
}

You may ask yourself "what just happened"??? Let me show you:

b = abcdefgh

* 0x0000000202020202 = 00000000 00000000 0000000a bcdefgha bcdefgha bcdefgha bcdefgha bcdefgh0
& 0x0000010884422010 = 00000000 00000000 00000001 00001000 10000100 01000010 00100000 00010000
                     = 00000000 00000000 0000000a 0000f000 b0000g00 0c0000h0 00d00000 000e0000

Note that we now have all the bits exactly once - they are just in a rather strange pattern. The modulo 1023 division "collapses" the bits of interest on top of each other - it's like magic, and I can't explain it. The result is indeed

hgfedcba

A slightly less obscure way to achieve the same thing (less efficient, but works for larger numbers quite efficiently) recognizes that if you swap adjacent bits , then adjacent bit pairs, then adjacent nibbles (4 bit groups), etc - you end up with a complete bit reversal. In that case, a byte reversal becomes

unsigned char bytereverse(unsigned char b) {
  b = (b & 0x55) << 1 | (b & 0xAA) >> 1; // swap adjacent bits
  b = (b & 0x33) << 2 | (b & 0xCC) >> 2; // swap adjacent pairs
  b = (b & 0x0F) << 4 | (b & 0xF0) >> 4; // swap nibbles
  return b;
}

In this case the following happens to byte b = abcdefgh:

b & 0x55 = abcdefgh & 01010101 = 0b0d0f0h << 1 = b0d0f0h0
b & 0xAA = abcdefgh & 10101010 = a0c0e0g0 >> 1 = 0a0c0e0g
OR these two to get badcfehg

Next line:

b & 0x33 = badcfehg & 00110011 = 00dc00hg << 2 = dc00hg00
b & 0xCC = badcfehg & 11001100 = ba00fe00 >> 2 = 00ba00fe
OR these to get dcbahgfe

last line:

b & 0x0F = dcbahgfe & 00001111 = 0000hgfe << 4 = hgfe0000
b & 0xF0 = dcbahgfe & 11110000 = dcba0000 >> 4 = 0000dcba
OR these to get hgfedcba

Which is the reversed byte you were after. It should be easy to see how just a couple more lines (similar to the above) get you to a reversed integer (32 bits). As the size of the number increases, this trick becomes more and more efficient, comparatively.

I trust that the answer you were looking for is "somewhere" in the above. If nothing else I hope you have a clearer understanding of the possibilities of bit manipulation in C.

Solution 3

If, as according to your comments, you want to shift one bit exactly, then one easy way to accomplish that would be this:

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

What your code does is reversing the bits; not rotating them. For instance, it would make 10111001 into 10011101, not 01110011.

Comments

[Dolda2000]

Yes. (c >> 1) | (c << 7)

[Floris]

I don't think this answer helps Manuel because he seems to be confused about what he is trying to do but I'm up voting because of the cool trick with reference!

[Moustache]

To add, if we don't know byte size of data type, I think we can do: (x >> n)|(x << sizeof(x)*8 - n)