在 C/C++ 中，反转字节中位顺序的最简单方法是什么？

In C/C++ what's the simplest way to reverse the order of bits in a byte?

提问by nathan

While there are multiple ways to reverse bit order in a byte, I'm curious as to what is the "simplest" for a developer to implement. And by reversing I mean:

虽然有多种方法可以反转字节中的位顺序，但我很好奇开发人员要实现的“最简单”是什么。倒车我的意思是：

1110 -> 0111
0010 -> 0100

This is similar to, but not a duplicate of thisPHP question.

这与此PHP 问题类似，但不是重复。

This is similar to, but not a duplicate of thisC question. This question is asking for the easiest method to implement by a developer. The "Best Algorithm" is concerned with memory and cpu performance.

这类似于但不是这个C 问题的重复。这个问题要求开发人员实现最简单的方法。“最佳算法”与内存和 CPU 性能有关。

采纳答案by e.James

If you are talking about a single byte, a table-lookup is probably the best bet, unless for some reason you don't have 256 bytes available.

如果您谈论的是单个字节，那么查找表可能是最好的选择，除非由于某种原因您没有 256 个字节可用。

回答by sth

This should work:

这应该有效：

unsigned char reverse(unsigned char b) {
   b = (b & 0xF0) >> 4 | (b & 0x0F) << 4;
   b = (b & 0xCC) >> 2 | (b & 0x33) << 2;
   b = (b & 0xAA) >> 1 | (b & 0x55) << 1;
   return b;
}

First the left four bits are swapped with the right four bits. Then all adjacent pairs are swapped and then all adjacent single bits. This results in a reversed order.

首先左四位与右四位交换。然后交换所有相邻的对，然后交换所有相邻的单个位。这导致相反的顺序。

回答by deft_code

I think a lookup table has to be one of the simplest methods. However, you don't need a full lookup table.

我认为查找表必须是最简单的方法之一。但是，您不需要完整的查找表。

//Index 1==0b0001 => 0b1000
//Index 7==0b0111 => 0b1110
//etc
static unsigned char lookup[16] = {
0x0, 0x8, 0x4, 0xc, 0x2, 0xa, 0x6, 0xe,
0x1, 0x9, 0x5, 0xd, 0x3, 0xb, 0x7, 0xf, };

uint8_t reverse(uint8_t n) {
   // Reverse the top and bottom nibble then swap them.
   return (lookup[n&0b1111] << 4) | lookup[n>>4];
}

// Detailed breakdown of the math
//  + lookup reverse of bottom nibble
//  |       + grab bottom nibble
//  |       |        + move bottom result into top nibble
//  |       |        |     + combine the bottom and top results 
//  |       |        |     | + lookup reverse of top nibble
//  |       |        |     | |       + grab top nibble
//  V       V        V     V V       V
// (lookup[n&0b1111] << 4) | lookup[n>>4]

This fairly simple to code and verify visually.
Ultimately this might even be faster than a full table. The bit arith is cheap and the table easily fits on a cache line.

这相当容易编码和视觉验证。
最终，这甚至可能比全表更快。位算法很便宜，并且该表很容易适合缓存行。

回答by Arkku

See the bit twiddling hacksfor many solutions. Copypasting from there is obviously simple to implement. =)

有关许多解决方案，请参阅bit twiddling hacks。从那里复制粘贴显然很容易实现。=)

For example (on a 32-bit CPU):

例如（在 32 位 CPU 上）：

uint8_t b = byte_to_reverse;
b = ((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16;

If by “simple to implement” one means something that can be done without a reference in an exam or job interview, then the safest bet is probably the inefficient copying of bits one by one into another variable in reverse order (already shown in other answers).

如果“简单实施”意味着在考试或工作面试中无需参考就可以完成的事情，那么最安全的选择可能是将比特以相反的顺序一个接一个地低效复制到另一个变量中（已在其他答案中显示） ）。

回答by fredoverflow

Since nobody posted a complete table lookup solution, here is mine:

由于没有人发布完整的查表解决方案，这里是我的：

unsigned char reverse_byte(unsigned char x)
{
    static const unsigned char table[] = {
        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,
    };
    return table[x];
}

回答by andand

template <typename T>
T reverse(T n, size_t b = sizeof(T) * CHAR_BIT)
{
    assert(b <= std::numeric_limits<T>::digits);

    T rv = 0;

    for (size_t i = 0; i < b; ++i, n >>= 1) {
        rv = (rv << 1) | (n & 0x01);
    }

    return rv;
}

EDIT:

编辑：

Converted it to a template with the optional bitcount

使用可选的 bitcount 将其转换为模板

回答by Daniel

Two lines:

两行：

for(i=0;i<8;i++)
     reversed |= ((original>>i) & 0b1)<<(7-i);

or in case you have issues with the "0b1" part:

或者如果您对“0b1”部分有问题：

for(i=0;i<8;i++)
     reversed |= ((original>>i) & 1)<<(7-i);

"original" is the byte you want to reverse. "reversed" is the result, initialized to 0.

“原始”是您要反转的字节。“反转”是结果，初始化为 0。

回答by Thomas Matthews

Although probably not portable, I would use assembly language.
Many assembly languages have instructions to rotate a bit into the carry flag and to rotate the carry flag into the word (or byte).

虽然可能不可移植，但我会使用汇编语言。
许多汇编语言都有将位旋转到进位标志并将进位标志旋转到字（或字节）的指令。

The algorithm is:

算法是：

for each bit in the data type:
  rotate bit into carry flag
  rotate carry flag into destination.
end-for

The high level language code for this is much more complicated, because C and C++ do not support rotating to carry and rotating from carry. The carry flag has to modeled.

用于此的高级语言代码要复杂得多，因为 C 和 C++ 不支持旋转进位和从进位旋转。进位标志必须建模。

Edit:Assembly language for example

编辑：例如汇编语言

;  Enter with value to reverse in R0.
;  Assume 8 bits per byte and byte is the native processor type.
   LODI, R2  8       ; Set up the bit counter
Loop:
   RRC, R0           ; Rotate R0 right into the carry bit.
   RLC, R1           ; Rotate R1 left, then append carry bit.
   DJNZ, R2  Loop    ; Decrement R2 and jump if non-zero to "loop"
   LODR, R0  R1      ; Move result into R0.

回答by dau_sama

I find the following solution simpler than the other bit fiddling algorithms I've seen in here.

我发现以下解决方案比我在这里看到的其他位摆弄算法更简单。

unsigned char reverse_byte(char a)
{

  return ((a & 0x1)  << 7) | ((a & 0x2)  << 5) |
         ((a & 0x4)  << 3) | ((a & 0x8)  << 1) |
         ((a & 0x10) >> 1) | ((a & 0x20) >> 3) |
         ((a & 0x40) >> 5) | ((a & 0x80) >> 7);
}

It gets every bit in the byte, and shifts it accordingly, starting from the first to the last.

它获取字节中的每一位，并相应地移动它，从第一个到最后一个。

Explanation:

解释：

   ((a & 0x1) << 7) //get first bit on the right and shift it into the first left position 
 | ((a & 0x2) << 5) //add it to the second bit and shift it into the second left position
  //and so on

回答by sth

The simplestway is probably to iterate over the bit positions in a loop:

在最简单的方法可能是遍历在一个循环中位的位置：

unsigned char reverse(unsigned char c) {
   int shift;
   unsigned char result = 0;
   for (shift = 0; shift < CHAR_BIT; shift++) {
      if (c & (0x01 << shift))
         result |= (0x80 >> shift);
   }
   return result;
}