2

I am new to bit manipulation. My friend recently asked me this in an interview. Given an array of bytes Eg: 1000100101010101 | 001010011100 We need to flip it two bits at a time horizontally inplace. So the new array should be: 1000 | 0101 and so on.

and so on. I think we start from the middle (marked by | here) and continue our way outwards taking two bits at a time. I know how to reverse single bits in a number at a time like this:

unsigned int reverse(unsigned int num)
{
    unsigned int  x = sizeof(num) * 8;
    unsigned int reverse_num = 0, i, temp;

    for (i = 0; i < x; i++)
    {
        temp = (num & (1 << i));
        if(temp)
            reverse_num |= (1 << ((x - 1) - i));
    }

    return reverse_num;
}

But I wonder how can we reverse two bits efficiently inplace. Thanks in advance.

Deepti Jain
  • 1,901
  • 4
  • 21
  • 29
  • 1
    How did you get `1000 | 0101` ? Don't you have a typo there? – LihO Feb 21 '12 at 19:27
  • 1
    Your given array of bytes appears to be (16-bits | 12-bits), for a total of 28-bits, or not a whole number of bytes. That also means your | is not in the middle. Please clarify. – abelenky Feb 21 '12 at 19:28
  • 1
    Are you asking about http://stackoverflow.com/questions/746171/best-algorithm-for-bit-reversal-from-msb-lsb-to-lsb-msb-in-c – alexander Feb 21 '12 at 19:33

2 Answers2

2

I'd just do a whole byte (or more) at once:

output = (input & 0x55) << 1;
output |= (input & 0xAA) >> 1;
Carl Norum
  • 219,201
  • 40
  • 422
  • 469
0

The "trick" way to do this is to precompute a table of bytes with the bits flipped. Then you can just index the table using a byte from the array, and write it back. As others have said - how many bits are in your bytes here?

Jeff
  • 1,969
  • 3
  • 21
  • 35