实现以下目标最有效的算法是什么:
0010 0000 => 0000 0100
从MSB->LSB转换为LSB->MSB。所有位都必须反转;也就是说，这不是字节交换。
当前回答
这是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中。
其他回答
对于其他可能遇到这个问题的网络搜索者，这里有一个总结(针对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;
}
我很好奇原始旋转有多快。 在我的机器(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);
}
unsigned char ReverseBits(unsigned char data)
{
unsigned char k = 0, rev = 0;
unsigned char n = data;
while(n)
{
k = n & (~(n - 1));
n &= (n - 1);
rev |= (128 / k);
}
return rev;
}
通用的
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);
我的简单解决方案
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;
