实现以下目标最有效的算法是什么:
0010 0000 => 0000 0100
从MSB->LSB转换为LSB->MSB。所有位都必须反转;也就是说，这不是字节交换。
当前回答
这个线程引起了我的注意，因为它处理了一个简单的问题，即使对于现代CPU也需要大量的工作(CPU周期)。有一天我也站在那里，有同样的¤#%“#”问题。我得翻几百万字节。然而，我知道我所有的目标系统都是基于现代英特尔的，所以让我们开始优化到极致!!
所以我使用了Matt J的查找代码作为基础。我正在基准测试的系统是i7 haswell 4700eq。
Matt J的查找位翻转400亿字节:大约0.272秒。
然后我继续尝试，看看英特尔的ISPC编译器是否可以向量化反向的算术。c。
我不打算在这里用我的发现来烦你，因为我尝试了很多来帮助编译器找到东西，无论如何，我最终得到了大约0.15秒的性能来bitflip 400亿字节。这是一个伟大的减少，但对于我的应用程序，这仍然是方式方式太慢。
所以人们让我展示世界上最快的基于英特尔的bitflipper。定时:
时间到bitflip 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，所以这是我能实现的最快速度。你能做一个快一点的版本吗?
关于使用Intel C/ c++编译器内在等效命令，请不要发表任何评论…
其他回答
原生ARM指令“rbit”可以用1个cpu周期和1个额外的cpu寄存器来完成，不可能被击败。
这个线程引起了我的注意，因为它处理了一个简单的问题，即使对于现代CPU也需要大量的工作(CPU周期)。有一天我也站在那里，有同样的¤#%“#”问题。我得翻几百万字节。然而，我知道我所有的目标系统都是基于现代英特尔的，所以让我们开始优化到极致!!
所以我使用了Matt J的查找代码作为基础。我正在基准测试的系统是i7 haswell 4700eq。
Matt J的查找位翻转400亿字节:大约0.272秒。
然后我继续尝试，看看英特尔的ISPC编译器是否可以向量化反向的算术。c。
我不打算在这里用我的发现来烦你，因为我尝试了很多来帮助编译器找到东西，无论如何，我最终得到了大约0.15秒的性能来bitflip 400亿字节。这是一个伟大的减少，但对于我的应用程序，这仍然是方式方式太慢。
所以人们让我展示世界上最快的基于英特尔的bitflipper。定时:
时间到bitflip 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，所以这是我能实现的最快速度。你能做一个快一点的版本吗?
关于使用Intel C/ c++编译器内在等效命令，请不要发表任何评论…
对于喜欢递归的人来说，这是另一个解决方案。
这个想法很简单。 将输入除以一半并交换两部分，继续直到达到单个位。
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
通用的
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);
当然，玩弄比特的黑客的明显来源是: http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious
