实现以下目标最有效的算法是什么:
0010 0000 => 0000 0100
从MSB->LSB转换为LSB->MSB。所有位都必须反转;也就是说,这不是字节交换。
实现以下目标最有效的算法是什么:
0010 0000 => 0000 0100
从MSB->LSB转换为LSB->MSB。所有位都必须反转;也就是说,这不是字节交换。
当前回答
好吧,这肯定不会是一个像Matt J的答案,但希望它仍然有用。
size_t reverse(size_t n, unsigned int bytes)
{
__asm__("BSWAP %0" : "=r"(n) : "0"(n));
n >>= ((sizeof(size_t) - bytes) * 8);
n = ((n & 0xaaaaaaaaaaaaaaaa) >> 1) | ((n & 0x5555555555555555) << 1);
n = ((n & 0xcccccccccccccccc) >> 2) | ((n & 0x3333333333333333) << 2);
n = ((n & 0xf0f0f0f0f0f0f0f0) >> 4) | ((n & 0x0f0f0f0f0f0f0f0f) << 4);
return n;
}
这与Matt的最佳算法完全相同,除了有一个叫做BSWAP的小指令,它交换64位数字的字节(而不是位)。所以b7 b6 b5 b4 b3 b2 b1 b0变成了b0 b1 b2 b3 b4 b5 b6 b7。由于我们处理的是32位数字,所以需要将字节交换后的数字向下移动32位。这只留给我们交换每个字节的8位的任务,这是完成的,瞧!我们做完了。
计时:在我的机器上,Matt的算法每次试验只需0.52秒。我的每次试验大约耗时0.42秒。我认为快20%还不错。
如果你担心指令BSWAP的可用性,维基百科列出了指令BSWAP是与1989年推出的80846一起添加的。值得注意的是,维基百科还指出,这条指令只适用于32位寄存器,这显然不是我的机器上的情况,它只适用于64位寄存器。
此方法同样适用于任何整型数据类型,因此可以通过传递所需的字节数来简单地推广该方法:
size_t reverse(size_t n, unsigned int bytes)
{
__asm__("BSWAP %0" : "=r"(n) : "0"(n));
n >>= ((sizeof(size_t) - bytes) * 8);
n = ((n & 0xaaaaaaaaaaaaaaaa) >> 1) | ((n & 0x5555555555555555) << 1);
n = ((n & 0xcccccccccccccccc) >> 2) | ((n & 0x3333333333333333) << 2);
n = ((n & 0xf0f0f0f0f0f0f0f0) >> 4) | ((n & 0x0f0f0f0f0f0f0f0f) << 4);
return n;
}
它可以被称为:
n = reverse(n, sizeof(char));//only reverse 8 bits
n = reverse(n, sizeof(short));//reverse 16 bits
n = reverse(n, sizeof(int));//reverse 32 bits
n = reverse(n, sizeof(size_t));//reverse 64 bits
编译器应该能够优化掉额外的形参(假设编译器内联了函数),对于sizeof(size_t)情况,右移将被完全删除。注意,如果传递sizeof(char), GCC至少不能删除BSWAP和右移。
其他回答
高效意味着吞吐量或延迟。
从头到尾,看看安德斯·塞德罗尼厄斯的回答,很好。
为了降低延迟,我推荐以下代码:
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
这不是人类能做的工作!... 但非常适合做机器
这是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()。
我认为这是最简单的逆转比特的方法之一。 如果这个逻辑有什么缺陷,请让我知道。 基本上在这个逻辑中,我们检查位置的位的值。 如果值为1,则在反转位置上设置位。
void bit_reverse(ui32 *data)
{
ui32 temp = 0;
ui32 i, bit_len;
{
for(i = 0, bit_len = 31; i <= bit_len; i++)
{
temp |= (*data & 1 << i)? (1 << bit_len-i) : 0;
}
*data = temp;
}
return;
}
实现低内存和最快。
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;
}
对于喜欢递归的人来说,这是另一个解决方案。
这个想法很简单。 将输入除以一半并交换两部分,继续直到达到单个位。
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