对于其他可能遇到这个问题的网络搜索者，这里有一个总结(针对C和JavaScript)。

对于JavaScript的完整解决方案，我们可以首先生成表:

const BIT_REVERSAL_TABLE = new Array(256)

for (var i = 0; i < 256; ++i) {
  var v = i, r = i, s = 7;
  for (v >>>= 1; v; v >>>= 1) {
    r <<= 1;
    r |= v & 1;
    --s;
  }
  BIT_REVERSAL_TABLE[i] = (r << s) & 0xff;
}

这给了我们BIT_REVERSAL_TABLE，这是@MattJ发布的:

const BIT_REVERSAL_TABLE = new Uint8Array([      
  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
])

8位、16位和32位无符号整数的算法可以在这里找到:

function reverseBits8(n) {
  return BIT_REVERSAL_TABLE[n]
}

function reverseBits16(n) {
  return (BIT_REVERSAL_TABLE[(n >> 8) & 0xff] |
    BIT_REVERSAL_TABLE[n & 0xff] << 8)
}

function reverseBits32(n) {
  return (BIT_REVERSAL_TABLE[n & 0xff] << 24) |
    (BIT_REVERSAL_TABLE[(n >>> 8) & 0xff] << 16) |
    (BIT_REVERSAL_TABLE[(n >>> 16) & 0xff] << 8) |
    BIT_REVERSAL_TABLE[(n >>> 24) & 0xff];
}

注意，32位版本不能在JavaScript中工作(必须转换为使用bigint，这很简单)，但应该可以在64位语言中工作:

log8(0b11000100)
log16(0b1110001001001100)
log32(0b11110010111110111100110010101011)

// 0b11000100 => 0b00100011
// 0b1110001001001100 => 0b0011001001000111
// doesn't work in JS it seems:
// 0b11110010111110111100110010101011 => 0b0-101010110011000010000010110001

function log8(n) {
  console.log(`${bits(n, 8)} => ${bits(reverseBits8(n), 8)}`)
}

function log16(n) {
  console.log(`${bits(n, 16)} => ${bits(reverseBits16(n), 16)}`)
}

function log32(n) {
  console.log(`${bits(n, 32)} => ${bits(reverseBits32(n), 32)}`)
}

function bits(n, size) {
  return `0b${n.toString(2).padStart(size, '0')}`
}

注意:这个解决方案适用于JavaScript的32位:

function reverseBits32(n) {
  let res = 0;
  for (let i = 0; i < 32; i++) {
    res = (res << 1) + (n & 1);
    n = n >>> 1;
  }

  return res >>> 0;
}

所有3个基于表格的解决方案都可以在C中正常工作。下面是一个粗略的C版本:

#include <stdlib.h>

static uint8_t* BIT_REVERSAL_TABLE;

uint8_t* 
make_bit_reversal_table() {
  uint8_t *table = malloc(256 * sizeof(uint8_t));
  uint8_t i;
  for (i = 0; i < 256 ; ++i) {
    uint8_t v = i;
    uint8_t r = i;
    uint8_t s = 7;
    for (v = v >> 1; v; v = v >> 1) {
      r <<= 1;
      r |= v & 1;
      --s;
    }
    table[i] = (r << s) & 0xff;
  }
  return table;
}

uint8_t 
reverse_bits_8(uint8_t n) {
  return BIT_REVERSAL_TABLE[n];
}

uint16_t
reverse_bits_16(uint16_t n)
{
  return (BIT_REVERSAL_TABLE[(n >> 8) & 0xff]
    | BIT_REVERSAL_TABLE[n & 0xff] << 8);
}

uint32_t
reverse_bits_32(uint32_t n) {
  return (BIT_REVERSAL_TABLE[n & 0xff] << 24) 
    | (BIT_REVERSAL_TABLE[(n >> 8) & 0xff] << 16) 
    | (BIT_REVERSAL_TABLE[(n >> 16) & 0xff] << 8) 
    | BIT_REVERSAL_TABLE[(n >> 24) & 0xff];
}

int 
main(void) {
  BIT_REVERSAL_TABLE = make_bit_reversal_table();
  return 0;
}

您可能希望使用标准模板库。它可能比上面提到的代码慢。然而，在我看来，这似乎更清楚，更容易理解。

 #include<bitset>
 #include<iostream>


 template<size_t N>
 const std::bitset<N> reverse(const std::bitset<N>& ordered)
 {
      std::bitset<N> reversed;
      for(size_t i = 0, j = N - 1; i < N; ++i, --j)
           reversed[j] = ordered[i];
      return reversed;
 };


 // test the function
 int main()
 {
      unsigned long num; 
      const size_t N = sizeof(num)*8;

      std::cin >> num;
      std::cout << std::showbase << std::hex;
      std::cout << "ordered  = " << num << std::endl;
      std::cout << "reversed = " << reverse<N>(num).to_ulong()  << std::endl;
      std::cout << "double_reversed = " << reverse<N>(reverse<N>(num)).to_ulong() << std::endl;  
 }

另一个基于循环的解决方案，在数量较低时快速退出(在c++中用于多种类型)

template<class T>
T reverse_bits(T in) {
    T bit = static_cast<T>(1) << (sizeof(T) * 8 - 1);
    T out;

    for (out = 0; bit && in; bit >>= 1, in >>= 1) {
        if (in & 1) {
            out |= bit;
        }
    }
    return out;
}

或者C语言中unsigned int

unsigned int reverse_bits(unsigned int in) {
    unsigned int bit = 1u << (sizeof(T) * 8 - 1);
    unsigned int out;

    for (out = 0; bit && in; bit >>= 1, in >>= 1) {
        if (in & 1)
            out |= bit;
    }
    return out;
}

我很好奇原始旋转有多快。 在我的机器(i7@2600)上，1,500,150,000次迭代的平均值为27.28 ns(在131,071个64位整数的随机集上)。

优点:占用内存少，代码简单。我想说它也没有那么大。对于任何输入(128个算术SHIFT运算+ 64个逻辑and运算+ 64个逻辑OR运算)，所需的时间都是可预测的常量。

我比较了@Matt J获得的最佳时间，他有公认的答案。如果我没有看错他的答案，他得到的最好结果是0.631739秒，100万次迭代，这导致平均每次旋转631 ns。

我使用的代码片段如下:

unsigned long long reverse_long(unsigned long long x)
{
    return (((x >> 0) & 1) << 63) |
           (((x >> 1) & 1) << 62) |
           (((x >> 2) & 1) << 61) |
           (((x >> 3) & 1) << 60) |
           (((x >> 4) & 1) << 59) |
           (((x >> 5) & 1) << 58) |
           (((x >> 6) & 1) << 57) |
           (((x >> 7) & 1) << 56) |
           (((x >> 8) & 1) << 55) |
           (((x >> 9) & 1) << 54) |
           (((x >> 10) & 1) << 53) |
           (((x >> 11) & 1) << 52) |
           (((x >> 12) & 1) << 51) |
           (((x >> 13) & 1) << 50) |
           (((x >> 14) & 1) << 49) |
           (((x >> 15) & 1) << 48) |
           (((x >> 16) & 1) << 47) |
           (((x >> 17) & 1) << 46) |
           (((x >> 18) & 1) << 45) |
           (((x >> 19) & 1) << 44) |
           (((x >> 20) & 1) << 43) |
           (((x >> 21) & 1) << 42) |
           (((x >> 22) & 1) << 41) |
           (((x >> 23) & 1) << 40) |
           (((x >> 24) & 1) << 39) |
           (((x >> 25) & 1) << 38) |
           (((x >> 26) & 1) << 37) |
           (((x >> 27) & 1) << 36) |
           (((x >> 28) & 1) << 35) |
           (((x >> 29) & 1) << 34) |
           (((x >> 30) & 1) << 33) |
           (((x >> 31) & 1) << 32) |
           (((x >> 32) & 1) << 31) |
           (((x >> 33) & 1) << 30) |
           (((x >> 34) & 1) << 29) |
           (((x >> 35) & 1) << 28) |
           (((x >> 36) & 1) << 27) |
           (((x >> 37) & 1) << 26) |
           (((x >> 38) & 1) << 25) |
           (((x >> 39) & 1) << 24) |
           (((x >> 40) & 1) << 23) |
           (((x >> 41) & 1) << 22) |
           (((x >> 42) & 1) << 21) |
           (((x >> 43) & 1) << 20) |
           (((x >> 44) & 1) << 19) |
           (((x >> 45) & 1) << 18) |
           (((x >> 46) & 1) << 17) |
           (((x >> 47) & 1) << 16) |
           (((x >> 48) & 1) << 15) |
           (((x >> 49) & 1) << 14) |
           (((x >> 50) & 1) << 13) |
           (((x >> 51) & 1) << 12) |
           (((x >> 52) & 1) << 11) |
           (((x >> 53) & 1) << 10) |
           (((x >> 54) & 1) << 9) |
           (((x >> 55) & 1) << 8) |
           (((x >> 56) & 1) << 7) |
           (((x >> 57) & 1) << 6) |
           (((x >> 58) & 1) << 5) |
           (((x >> 59) & 1) << 4) |
           (((x >> 60) & 1) << 3) |
           (((x >> 61) & 1) << 2) |
           (((x >> 62) & 1) << 1) |
           (((x >> 63) & 1) << 0);
}

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

这是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.