reverse the bits using bit field in c language?

how to reverse the bits using bit wise ope开发者_JS百科rators in c language

Eg:

i/p: 10010101
o/p: 10101001

If it's just 8 bits:

u_char in = 0x95;
u_char out = 0;
for (int i = 0; i < 8; ++i) {
    out <<= 1;
    out |= (in & 0x01);
    in >>= 1;
}

Or for bonus points:

u_char in = 0x95;
u_char out = in;
out = (out & 0xaa) >> 1 | (out & 0x55) << 1;
out = (out & 0xcc) >> 2 | (out & 0x33) << 2;
out = (out & 0xf0) >> 4 | (out & 0x0f) << 4;

figuring out how the last one works is an exercise for the reader ;-)

Knuth has a section on Bit reversal in The Art of Computer Programming Vol 4A, bitwise tricks and techniques.

To reverse the bits of a 32 bit number in a divide and conquer fashion he uses magic constants

u0= 1010101010101010, (from -1/(2+1)

u1= 0011001100110011, (from -1/(4+1)

u2= 0000111100001111, (from -1/(16+1)

u3= 0000000011111111, (from -1/(256+1)

Method credited to Henry Warren Jr., Hackers delight.

    unsigned int u0 = 0x55555555;
    x = (((x >> 1) & u0) | ((x & u0) << 1));
    unsigned int u1 = 0x33333333;
    x = (((x >> 2) & u1) | ((x & u1) << 2));
    unsigned int u2 = 0x0f0f0f0f;
    x = (((x >> 4) & u2) | ((x & u2) << 4));
    unsigned int u3 = 0x00ff00ff;
    x = (((x >> 8) & u3) | ((x & u3) << 8));
    x = ((x >> 16) | (x << 16) mod 0x100000000); // reversed

The 16 and 8 bit cases are left as an exercise to the reader.

Well, this might not be the most elegant solution but it is a solution:

int reverseBits(int x) {
     int res = 0;
     int len = sizeof(x) * 8; // no of bits to reverse
     int i, shift, mask;

     for(i = 0; i < len; i++) {
          mask = 1 << i; //which bit we are at
          shift = len - 2*i - 1;
          mask &= x;
          mask = (shift > 0) ? mask << shift : mask >> -shift;
          res |= mask; // mask the bit we work at at shift it to the left     
     }

     return res;
}

Tested it on a sheet of paper and it seemed to work :D

Edit: Yeah, this is indeed very complicated. I dunno why, but I wanted to find a solution without touching the input, so this came to my haead