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

这是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()。

我认为下面是我所知道的最简单的方法。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.

对于喜欢递归的人来说，这是另一个解决方案。

这个想法很简单。 将输入除以一半并交换两部分，继续直到达到单个位。

Illustrated in the example below.

Ex : If Input is 00101010   ==> Expected output is 01010100

1. Divide the input into 2 halves 
    0010 --- 1010

2. Swap the 2 Halves
    1010     0010

3. Repeat the same for each half.
    10 -- 10 ---  00 -- 10
    10    10      10    00

    1-0 -- 1-0 --- 1-0 -- 0-0
    0 1    0 1     0 1    0 0

Done! Output is 01010100

这里有一个递归函数来求解。(注意，我使用了unsigned int，所以它可以用于sizeof(unsigned int)*8位的输入。

递归函数有两个参数-需要位的值 要反转的值和值中的比特数。

int reverse_bits_recursive(unsigned int num, unsigned int numBits)
{
    unsigned int reversedNum;;
    unsigned int mask = 0;

    mask = (0x1 << (numBits/2)) - 1;

    if (numBits == 1) return num;
    reversedNum = reverse_bits_recursive(num >> numBits/2, numBits/2) |
                   reverse_bits_recursive((num & mask), numBits/2) << numBits/2;
    return reversedNum;
}

int main()
{
    unsigned int reversedNum;
    unsigned int num;

    num = 0x55;
    reversedNum = reverse_bits_recursive(num, 8);
    printf ("Bit Reversal Input = 0x%x Output = 0x%x\n", num, reversedNum);

    num = 0xabcd;
    reversedNum = reverse_bits_recursive(num, 16);
    printf ("Bit Reversal Input = 0x%x Output = 0x%x\n", num, reversedNum);

    num = 0x123456;
    reversedNum = reverse_bits_recursive(num, 24);
    printf ("Bit Reversal Input = 0x%x Output = 0x%x\n", num, reversedNum);

    num = 0x11223344;
    reversedNum = reverse_bits_recursive(num,32);
    printf ("Bit Reversal Input = 0x%x Output = 0x%x\n", num, reversedNum);
}

输出如下:

Bit Reversal Input = 0x55 Output = 0xaa
Bit Reversal Input = 0xabcd Output = 0xb3d5
Bit Reversal Input = 0x123456 Output = 0x651690
Bit Reversal Input = 0x11223344 Output = 0x22cc4488

通用的

C代码。以1字节输入数据num为例。

    unsigned char num = 0xaa;   // 1010 1010 (aa) -> 0101 0101 (55)
    int s = sizeof(num) * 8;    // get number of bits
    int i, x, y, p;
    int var = 0;                // make var data type to be equal or larger than num

    for (i = 0; i < (s / 2); i++) {
        // extract bit on the left, from MSB
        p = s - i - 1;
        x = num & (1 << p);
        x = x >> p;
        printf("x: %d\n", x);

        // extract bit on the right, from LSB
        y = num & (1 << i);
        y = y >> i;
        printf("y: %d\n", y);

        var = var | (x << i);       // apply x
        var = var | (y << p);       // apply y
    }

    printf("new: 0x%x\n", new);

下面这个怎么样:

    uint reverseMSBToLSB32ui(uint input)
    {
        uint output = 0x00000000;
        uint toANDVar = 0;
        int places = 0;

        for (int i = 1; i < 32; i++)
        {
            places = (32 - i);
            toANDVar = (uint)(1 << places);
            output |= (uint)(input & (toANDVar)) >> places;

        }


        return output;
    }

小而简单(不过只有32位)。

高效意味着吞吐量或延迟。

从头到尾，看看安德斯·塞德罗尼厄斯的回答，很好。

为了降低延迟，我推荐以下代码:

uint32_t reverseBits( uint32_t x )
{
#if defined(__arm__) || defined(__aarch64__)
    __asm__( "rbit %0, %1" : "=r" ( x ) : "r" ( x ) );
    return x;
#endif
    // Flip pairwise
    x = ( ( x & 0x55555555 ) << 1 ) | ( ( x & 0xAAAAAAAA ) >> 1 );
    // Flip pairs
    x = ( ( x & 0x33333333 ) << 2 ) | ( ( x & 0xCCCCCCCC ) >> 2 );
    // Flip nibbles
    x = ( ( x & 0x0F0F0F0F ) << 4 ) | ( ( x & 0xF0F0F0F0 ) >> 4 );

    // Flip bytes. CPUs have an instruction for that, pretty fast one.
#ifdef _MSC_VER
    return _byteswap_ulong( x );
#elif defined(__INTEL_COMPILER)
    return (uint32_t)_bswap( (int)x );
#else
    // Assuming gcc or clang
    return __builtin_bswap32( x );
#endif
}

编译器输出:https://godbolt.org/z/5ehd89