是否有内置函数来反转位顺序

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.

我想出了几种手动方式，但我一直想知道是否有内置的.NET可以做到这一点。

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

例如：1001 1101 = 9D将变为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

谢谢

6 个解决方案

#1

I decided to do some performance tests about reversing methods.

我决定做一些关于倒车方法的性能测试。

Using Chad's link I wrote the following methods:

使用Chad的链接我写了以下方法：

public static byte[] BitReverseTable =
{
    0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0,
    0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0,
    0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8,
    0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8,
    0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4,
    0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4,
    0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec,
    0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc,
    0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2,
    0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2,
    0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea,
    0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa,
    0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6,
    0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6,
    0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee,
    0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe,
    0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1,
    0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1,
    0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9,
    0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9,
    0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5,
    0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5,
    0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed,
    0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd,
    0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3,
    0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3,
    0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb,
    0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb,
    0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7,
    0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7,
    0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef,
    0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff
};
public static byte ReverseWithLookupTable(byte toReverse)
{
    return BitReverseTable[toReverse];
}
public static byte ReverseBitsWith4Operations(byte b)
{
    return (byte)(((b * 0x80200802ul) & 0x0884422110ul) * 0x0101010101ul >> 32);
}
public static byte ReverseBitsWith3Operations(byte b)
{
    return (byte)((b * 0x0202020202ul & 0x010884422010ul) % 1023);
}
public static byte ReverseBitsWith7Operations(byte b)
{
    return (byte)(((b * 0x0802u & 0x22110u) | (b * 0x8020u & 0x88440u)) * 0x10101u >> 16);
}
public static byte ReverseBitsWithLoop(byte v)
{
    byte r = v; // r will be reversed bits of v; first get LSB of v
    int s = 7; // extra shift needed at end
    for (v >>= 1; v != 0; v >>= 1)
    {
        r <<= 1;
        r |= (byte)(v & 1);
        s--;
    }
    r <<= s; // shift when v's highest bits are zero
    return r;
}
public static byte ReverseWithUnrolledLoop(byte b)
{
    byte r = b;
    b >>= 1;
    r <<= 1;
    r |= (byte)(b & 1);
    b >>= 1;

    r <<= 1;
    r |= (byte)(b & 1);
    b >>= 1;

    r <<= 1;
    r |= (byte)(b & 1);
    b >>= 1;

    r <<= 1;
    r |= (byte)(b & 1);
    b >>= 1;

    r <<= 1;
    r |= (byte)(b & 1);
    b >>= 1;

    r <<= 1;
    r |= (byte)(b & 1);
    b >>= 1;

    r <<= 1;
    r |= (byte)(b & 1);
    b >>= 1;

    return r;
}

---

Then I tested it, and here's the results:

然后我测试了它，结果如下：

Test features:

测试功能：

• 100000000 random bytes to reverse
• 100000000个随机字节来反转
• OS: Windows 7 x64
• 操作系统：Windows 7 x64
• CPU: AMD Phenom II 955 (4-core @ 3.2 GHz)
• CPU：AMD Phenom II 955（4核@ 3.2 GHz）
• RAM: 4GB
• 内存：4GB
• IDE: Visual Studio 2010
• IDE：Visual Studio 2010

Target framework 3.5

目标框架3.5

-----------------------------------------------------
|    Method     | Ticks(x64 mode) | Ticks(x86 mode) |
-----------------------------------------------------
| Loop          |   4861859       |   4079554       |
| Unrolled Loop |   3241781       |   2948026       |
| Look-up table |   894809        |   312410        |
| 3-Operations  |   2068072       |   6757008       |
| 4-Operations  |   893924        |   1972576       |
| 7-Operations  |   1219189       |   303499        |
-----------------------------------------------------

Target framework 4

目标框架4

-----------------------------------------------------
|    Method     | Ticks(x64 mode) | Ticks(x86 mode) |
-----------------------------------------------------
| Loop          |   4682654       |   4147036       |
| Unrolled Loop |   3154920       |   2851307       |
| Look-up table |   602686        |   313940        |
| 3-Operations  |   2067509       |   6661542       |
| 4-Operations  |   893406        |   2018334       |
| 7-Operations  |   1193200       |   991792        |
-----------------------------------------------------

So, look-up table method is not always the fastest :)

所以，查找表方法并不总是最快:)

That can be reasonable, because memory access is slower than CPU registers access, so if some method is compiled and optimized enough to avoid mem access (and to do few operations) it is faster. (Anyway, the gap is extremely reduced by CPU mem caching)

这可能是合理的，因为内存访问比CPU寄存器访问慢，所以如果编译和优化某些方法足以避免mem访问（并进行少量操作），则速度更快。 （无论如何，CPU内存缓存极大地减少了差距）

It's also interesting to see the different behaviours in case of x64 or x86 mode, and how 3.5 and 4.0 frameworks performs distinct optimizations.

在x64或x86模式下看到不同的行为，以及3.5和4.0框架如何执行不同的优化，这也很有趣。

#2

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

不，BCL中没有任何内容。

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).

  由于只有8位，因此展开循环（使用4个语句而不是for循环）是值得的。

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

  要获得更快的解决方案，请创建256条目查找表。

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

当然，您可以将两个方法都包装在一个函数中，以便使用只需要1个语句。

I found a page for this problem.

我找到了这个问题的页面。

#3

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

你可以在fxtbook中找到比特笨拙的算法。第1.14章给出了这些比特交换算法：

    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.

x86 JIT编译器在优化此代码方面做得不是很好。如果速度很重要，那么您可以使用它来初始化byte []以使其成为快速查找。

#4

Using @Chads link

使用@Chads链接

byte b; 
b = 0x9D;
b = (byte)((b * 0x0202020202 & 0x010884422010) % 1023); 

Edit: Forgot the cast

编辑：忘记演员

#5

Please see this comprehensive bit-twiddling hacks, namely you want 'Reverse the bits in a byte with 3 operations (64-bit multiply and modulus division)'

请看这个全面的比特笨拙的黑客攻击，即你想要'通过3次操作（64位乘法和模数除法）反转一个字节中的位'

int lVal = 0x9D;
int lNewVal = (int)((((ulong)lVal * 0x0202020202UL) & 0x010884422010UL) % 1023);
System.Diagnostics.Debug.WriteLine(string.Format("{0:X2}", lNewVal));

When you run this you will find that the value gets reversed to 0xB9.

当你运行它时，你会发现该值被反转为0xB9。

#6

private UInt32 BitReverse(UInt32 value)
{
  UInt32 left = (UInt32)1 << 31;
  UInt32 right = 1;
  UInt32 result = 0;

  for (int i = 31; i >= 1; i -= 2)
  {
    result |= (value & left) >> i;
    result |= (value & right) << i;
    left >>= 1;
    right <<= 1;
  }
  return result;
}