用C语言实现位反转(从MSB->LSB到LSB->MSB)的有效算法
实现以下目标的最有效算法是什么：
0010 0000 => 0000 0100
转换是从MSB->LSB到LSB->MSB。所有位都必须颠倒；也就是说，这不是字节序交换。
回答 21
Stack Overflow用户
发布于 2014-06-05 18:55:28
这个线程引起了我的注意，因为它处理了一个即使对于现代CPU也需要大量工作(CPU周期)的简单问题。有一天，我也遇到了同样的¤#%"#“问题。我不得不翻转数百万字节。然而，我知道我的所有目标系统都是基于现代Intel的，所以让我们开始最大限度地优化吧！
所以我使用Matt J的查找代码作为基础。我正在进行基准测试的系统是i7 haswell 4700eq。
Matt J的查找位翻转了400000000字节:大约0.272秒。
然后，我继续尝试，看看Intel的ISPC编译器是否可以向量化反向运算。c。
我不会在这里让你厌烦我的发现，因为我试了很多来帮助编译器找到东西，不管怎样，我最终只用了大约0.15秒的性能来bitflip 400,000,000字节。这是一个很大的缩减，但对于我的应用程序来说，这仍然太慢了。
所以人们让我来介绍世界上最快的基于Intel的bitflipper。计时时间：
位翻转时间400000000字节: 0.050082秒！
// Bitflip using AVX2 - The fastest Intel based bitflip in the world!!
// Made by Anders Cedronius 2014 (anders.cedronius (you know what) gmail.com)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <omp.h>
using namespace std;
#define DISPLAY_HEIGHT 4
#define DISPLAY_WIDTH 32
#define NUM_DATA_BYTES 400000000
// Constants (first we got the mask, then the high order nibble look up table and last we got the low order nibble lookup table)
__attribute__ ((aligned(32))) static unsigned char k1[32*3]={
0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,
0x00,0x08,0x04,0x0c,0x02,0x0a,0x06,0x0e,0x01,0x09,0x05,0x0d,0x03,0x0b,0x07,0x0f,0x00,0x08,0x04,0x0c,0x02,0x0a,0x06,0x0e,0x01,0x09,0x05,0x0d,0x03,0x0b,0x07,0x0f,
0x00,0x80,0x40,0xc0,0x20,0xa0,0x60,0xe0,0x10,0x90,0x50,0xd0,0x30,0xb0,0x70,0xf0,0x00,0x80,0x40,0xc0,0x20,0xa0,0x60,0xe0,0x10,0x90,0x50,0xd0,0x30,0xb0,0x70,0xf0
};
// The data to be bitflipped (+32 to avoid the quantization out of memory problem)
__attribute__ ((aligned(32))) static unsigned char data[NUM_DATA_BYTES+32]={};
extern "C" {
void bitflipbyte(unsigned char[],unsigned int,unsigned char[]);
}
int main()
{
for(unsigned int i = 0; i < NUM_DATA_BYTES; i++)
{
data[i] = rand();
}
printf ("\r\nData in(start):\r\n");
for (unsigned int j = 0; j < 4; j++)
{
for (unsigned int i = 0; i < DISPLAY_WIDTH; i++)
{
printf ("0x%02x,",data[i+(j*DISPLAY_WIDTH)]);
}
printf ("\r\n");
}
printf ("\r\nNumber of 32-byte chunks to convert: %d\r\n",(unsigned int)ceil(NUM_DATA_BYTES/32.0));
double start_time = omp_get_wtime();
bitflipbyte(data,(unsigned int)ceil(NUM_DATA_BYTES/32.0),k1);
double end_time = omp_get_wtime();
printf ("\r\nData out:\r\n");
for (unsigned int j = 0; j < 4; j++)
{
for (unsigned int i = 0; i < DISPLAY_WIDTH; i++)
{
printf ("0x%02x,",data[i+(j*DISPLAY_WIDTH)]);
}
printf ("\r\n");
}
printf("\r\n\r\nTime to bitflip %d bytes: %f seconds\r\n\r\n",NUM_DATA_BYTES, end_time-start_time);
// return with no errors
return 0;
}printf用于调试..
这是一匹主力马：
bits 64
global bitflipbyte
bitflipbyte:
vmovdqa ymm2, [rdx]
add rdx, 20h
vmovdqa ymm3, [rdx]
add rdx, 20h
vmovdqa ymm4, [rdx]
bitflipp_loop:
vmovdqa ymm0, [rdi]
vpand ymm1, ymm2, ymm0
vpandn ymm0, ymm2, ymm0
vpsrld ymm0, ymm0, 4h
vpshufb ymm1, ymm4, ymm1
vpshufb ymm0, ymm3, ymm0
vpor ymm0, ymm0, ymm1
vmovdqa [rdi], ymm0
add rdi, 20h
dec rsi
jnz bitflipp_loop
ret代码需要32个字节，然后屏蔽掉半字节。高位半字节右移4。然后我使用vpshufb和ymm4 / ymm3作为查找表。我可以使用一个单独的查找表，但是在ORing之前，我必须向左移动，再一次将这些小块放在一起。
还有更快的方法来翻转比特。但我使用的是单线程和CPU，所以这是我能达到的最快速度。你能做一个更快的版本吗？
请不要评论使用英特尔C/C++编译器内部等效命令...
Stack Overflow用户
发布于 2013-06-08 08:11:32
当然，这不会是一个像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指令的可用性，Wikipedia会列出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和右移位。
Stack Overflow用户
发布于 2015-08-19 18:34:32
Anders Cedronius's answer为拥有支持AVX2的x86处理器的用户提供了一个很好的解决方案。对于不支持AVX的x86平台或非x86平台，以下任何一种实现都应该可以很好地工作。
第一个代码是经典的二进制分区方法的变体，编码的目的是最大限度地使用在各种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展示了反转比特的聪明方法，这些方法比经典的二进制划分算法需要更少的操作，这有点令人惊讶。Hacker's Delight网站上的this document中显示了一种这样的32位操作数算法，我在TAOCP中找不到它。
/* 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;
}使用英特尔编译器C/C++编译器13.1.3.198，上述两个函数都能很好地自动向量化XMM寄存器。它们也可以不费很多力气就被手动矢量化。
在我的IvyBridge Xeon E3 1270v2上，使用自动矢量化代码，使用brev_classic()在0.070秒内位反转了一亿个uint32_t字，使用brev_knuth()在0.068秒内位反转。我小心翼翼地确保我的基准测试不受系统内存带宽的限制。
https://stackoverflow.com/questions/746171
复制相似问题