假设你有一个比特数组，怎么样: 1. 从MSB开始，将比特一个一个地推入堆栈。 2. 从这个堆栈弹出位到另一个数组(如果你想节省空间，也可以是同一个数组)，将第一个弹出位放入MSB，然后从那里继续到较低的有效位。

Stack stack = new Stack();
Bit[] bits = new Bit[] { 0, 0, 1, 0, 0, 0, 0, 0 };

for (int i = 0; i < bits.Length; i++) 
{
    stack.push(bits[i]);
}

for (int i = 0; i < bits.Length; i++)
{
    bits[i] = stack.pop();
}

实现低内存和最快。

private Byte  BitReverse(Byte bData)
    {
        Byte[] lookup = { 0, 8,  4, 12, 
                          2, 10, 6, 14 , 
                          1, 9,  5, 13,
                          3, 11, 7, 15 };
        Byte ret_val = (Byte)(((lookup[(bData & 0x0F)]) << 4) + lookup[((bData & 0xF0) >> 4)]);
        return ret_val;
    }

我认为下面是我所知道的最简单的方法。MSB是输入，LSB是“反向”输出:

unsigned char rev(char MSB) {
    unsigned char LSB=0;  // for output
    _FOR(i,0,8) {
        LSB= LSB << 1;
        if(MSB&1) LSB = LSB | 1;
        MSB= MSB >> 1;
    }
    return LSB;
}

//    It works by rotating bytes in opposite directions. 
//    Just repeat for each byte.

我的简单解决方案

BitReverse(IN)
    OUT = 0x00;
    R = 1;      // Right mask   ...0000.0001
    L = 0;      // Left mask    1000.0000...
    L = ~0; 
    L = ~(i >> 1);
    int size = sizeof(IN) * 4;  // bit size

    while(size--){
        if(IN & L) OUT = OUT | R; // start from MSB  1000.xxxx
        if(IN & R) OUT = OUT | L; // start from LSB  xxxx.0001
        L = L >> 1;
        R = R << 1; 
    }
    return OUT;

这不是人类能做的工作!．.． 但非常适合做机器

这是2015年，距离第一次提出这个问题已经过去了6年。编译器从此成为我们的主人，而我们作为人类的工作只是帮助它们。那么，把我们的意图传达给机器的最佳方式是什么呢?

位反转是如此普遍，以至于你不得不怀疑为什么x86不断增长的ISA没有包含一次性完成它的指令。

原因是:如果你给编译器一个真正简洁的意图，位反转应该只需要大约20个CPU周期。让我向你展示如何制作reverse()并使用它:

#include <inttypes.h>
#include <stdio.h>

uint64_t reverse(const uint64_t n,
                 const uint64_t k)
{
        uint64_t r, i;
        for (r = 0, i = 0; i < k; ++i)
                r |= ((n >> i) & 1) << (k - i - 1);
        return r;
}

int main()
{
        const uint64_t size = 64;
        uint64_t sum = 0;
        uint64_t a;
        for (a = 0; a < (uint64_t)1 << 30; ++a)
                sum += reverse(a, size);
        printf("%" PRIu64 "\n", sum);
        return 0;
}

使用Clang版本>= 3.6，-O3， -march=native(用Haswell测试)编译这个示例程序，使用新的AVX2指令提供美术质量代码，运行时为11秒处理~ 10亿reverse()秒。这是~10 ns每反向()，0.5 ns CPU周期假设2 GHz，我们将达到甜蜜的20个CPU周期。

对于单个大数组，您可以在访问RAM一次所需的时间内放入10个reverse() ! 你可以在访问L2缓存LUT两次的时间里放入1个reverse()。

注意:这个示例代码应该可以作为一个不错的基准运行几年，但是一旦编译器足够聪明，可以优化main()只输出最终结果，而不是真正计算任何东西，它最终就会开始显得过时了。但目前它只用于展示reverse()。

似乎许多其他帖子都关心速度(即最好=最快)。 简单性怎么样?考虑:

char ReverseBits(char character) {
    char reversed_character = 0;
    for (int i = 0; i < 8; i++) {
        char ith_bit = (c >> i) & 1;
        reversed_character |= (ith_bit << (sizeof(char) - 1 - i));
    }
    return reversed_character;
}

并希望聪明的编译器将为您优化。

如果你想反转一个更长的位列表(包含sizeof(char) * n位)，你可以使用这个函数得到:

void ReverseNumber(char* number, int bit_count_in_number) {
    int bytes_occupied = bit_count_in_number / sizeof(char);      

    // first reverse bytes
    for (int i = 0; i <= (bytes_occupied / 2); i++) {
        swap(long_number[i], long_number[n - i]);
    }

    // then reverse bits of each individual byte
    for (int i = 0; i < bytes_occupied; i++) {
         long_number[i] = ReverseBits(long_number[i]);
    }
}

这将把[10000000,10101010]反向转换为[01010101,00000001]。