Alex Rivera | Logout

Is there a built-in function to reverse bit order

Asked 2010-08-27T20:17:37.420
36

I've come up with several manual ways of doing this, but i keep wondering if there is something built-in .NET that does this.

Basically, i want to reverse the bit order in a byte, so that the least significant bit becomes the most significant bit.

For example: 1001 1101 = 9D would become 1011 1001 = B9

On of the ways to do this is to use bitwise operations if following this pseudo code:

for (i = 0; i<8; i++)
{
  Y>>1
  x= byte & 1
  byte >>1
  y = x|y;
}

I wonder if there is a function somewhere that will allow me to do all this in one single line. Also, do you know the term for such an operation, i'm sure there is one, but i can't remember it at the moment.

Thanks

c# .net bitwise-operators
Edit
Report

2 Answers

15

No, there isn't anything in the BCL for this.

But, assuming you want something fast:

  • Since there are only 8 bits, it pays to unroll the loop (use 4 statements instead of the for-loop).

  • For an even faster solution, create a 256 entry lookup table.

And you can of course wrap both methods in a function so that the usage only takes 1 statement.

I found a page for this problem.

answered 2010-08-27T20:24:32.307
4

You can find bit twiddling algorithms in the fxtbook. Chapter 1.14 gives these bit swapping algorithms:

    static uint bitSwap1(uint x) {
        uint m = 0x55555555;
        return ((x & m) << 1) | ((x & (~m)) >> 1);
    }
    static uint bitSwap2(uint x) {
        uint m = 0x33333333;
        return ((x & m) << 2) | ((x & (~m)) >> 2);
    }
    static uint bitSwap4(uint x) {
        uint m = 0x0f0f0f0f;
        return ((x & m) << 4) | ((x & (~m)) >> 4);
    }

Which makes your byte value bit reversal:

    public static byte swapBits(byte value) {
        return (byte)(bitSwap4(bitSwap2(bitSwap1(value))));
    }

The x86 JIT compiler doesn't do a great job optimizing this code. If speed matters then you could use it to initialize a byte[] to make it a fast lookup instead.

answered 2010-08-27T20:52:49.590

Your Answer