实现以下目标最有效的算法是什么:
0010 0000 => 0000 0100
从MSB->LSB转换为LSB->MSB。所有位都必须反转;也就是说，这不是字节交换。
当前回答
Anders Cedronius的答案为那些拥有支持AVX2的x86 CPU的人提供了一个很好的解决方案。对于没有AVX支持的x86平台或非x86平台，以下任何一种实现都应该工作良好。
第一个代码是经典二进制分区方法的一个变体，编码的目的是最大限度地利用shift-plus-logic习惯用法，这种习惯用法在各种ARM处理器上都很有用。此外，它使用动态掩码生成，这对于需要多个指令来加载每个32位掩码值的RISC处理器是有益的。x86平台的编译器应该在编译时而不是运行时使用常量传播来计算所有掩码。
/* Classic binary partitioning algorithm */
inline uint32_t brev_classic (uint32_t a)
{
uint32_t m;
a = (a >> 16) | (a << 16); // swap halfwords
m = 0x00ff00ff; a = ((a >> 8) & m) | ((a << 8) & ~m); // swap bytes
m = m^(m << 4); a = ((a >> 4) & m) | ((a << 4) & ~m); // swap nibbles
m = m^(m << 2); a = ((a >> 2) & m) | ((a << 2) & ~m);
m = m^(m << 1); a = ((a >> 1) & m) | ((a << 1) & ~m);
return a;
}
在“计算机编程艺术”的第4A卷中，D. Knuth展示了反转位的聪明方法，这比经典的二进制分区算法所需的操作少得令人惊讶。一个这样的32位操作数算法，我在TAOCP中找不到，在Hacker’s Delight网站上的这个文档中显示。
/* Knuth's algorithm from http://www.hackersdelight.org/revisions.pdf. Retrieved 8/19/2015 */
inline uint32_t brev_knuth (uint32_t a)
{
uint32_t t;
a = (a << 15) | (a >> 17);
t = (a ^ (a >> 10)) & 0x003f801f;
a = (t + (t << 10)) ^ a;
t = (a ^ (a >> 4)) & 0x0e038421;
a = (t + (t << 4)) ^ a;
t = (a ^ (a >> 2)) & 0x22488842;
a = (t + (t << 2)) ^ a;
return a;
}
使用Intel编译器C/ c++编译器13.1.3.198，上述两个函数都能很好地自动向量化XMM寄存器。它们也可以手动向量化，而不需要很多努力。
在我的IvyBridge Xeon E3 1270v2上，使用自动向量化代码，1亿uint32_t字在0.070秒内使用brev_classic()位反转，0.068秒使用brev_knuth()位反转。我注意确保我的基准测试不受系统内存带宽的限制。
其他回答
对于其他可能遇到这个问题的网络搜索者，这里有一个总结(针对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;
}
这是32位，如果我们考虑8位，我们需要改变大小。
void bitReverse(int num)
{
int num_reverse = 0;
int size = (sizeof(int)*8) -1;
int i=0,j=0;
for(i=0,j=size;i<=size,j>=0;i++,j--)
{
if((num >> i)&1)
{
num_reverse = (num_reverse | (1<<j));
}
}
printf("\n rev num = %d\n",num_reverse);
}
按LSB->MSB顺序读取输入整数“num”，并按MSB->LSB顺序存储在num_reverse中。
下面这个怎么样:
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位)。
我很好奇原始旋转有多快。 在我的机器(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);
}
我认为下面是我所知道的最简单的方法。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.
