algorithm - 在C里面,最佳的位反转算法( 从MSB >LSB到LSB >MSB )

实现以下目标的最佳算法是什么:

0010 0000 => 0000 0100

从MSB- >到LSB- > MSB的转换,所有位必须反转; 也就是说,这不是字节顺序交换。

时间:

注:以下所有算法均为C,但可移植到你的选择语言(当发现他们不那么快的时候不要找我),

选项

低内存(32位int 32位机器)(来自这里 ):


unsigned int
reverse(register unsigned int x)
{
 x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
 x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2));
 x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4));
 x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8));
 return((x >> 16) | (x << 16));

}

来自著名的Bit Twiddling Hacks页面 :

最快的(查找表):


static const unsigned char BitReverseTable256[] = 
{
 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
};

unsigned int v; // reverse 32-bit value, 8 bits at time
unsigned int c; // c will get v reversed

// Option 1:
c = (BitReverseTable256[v & 0xff] << 24) | 
 (BitReverseTable256[(v >> 8) & 0xff] << 16) | 
 (BitReverseTable256[(v >> 16) & 0xff] << 8) |
 (BitReverseTable256[(v >> 24) & 0xff]);

// Option 2:
unsigned char * p = (unsigned char *) &v;
unsigned char * q = (unsigned char *) &c;
q[3] = BitReverseTable256[p[0]]; 
q[2] = BitReverseTable256[p[1]]; 
q[1] = BitReverseTable256[p[2]]; 
q[0] = BitReverseTable256[p[3]];

你可以将这个想法扩展到64位int s,或者为速度(假设你的l1数据缓存足够大)交换内存,并在一个64K-entry查找表中反转16-bits 。


其他

简单


unsigned int v; // input bits to be reversed
unsigned int r = v; // r will be reversed bits of v; first get LSB of v
int s = sizeof(v) * CHAR_BIT - 1; // extra shift needed at end

for (v >>= 1; v; v >>= 1)
{ 
 r <<= 1;
 r |= v & 1;
 s--;
}
r <<= s; // shift when v's highest bits are zero

更快的(32位处理器)


unsigned char b = x;
b = ((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16; 

更快的(64位处理器)


unsigned char b; // reverse this (8-bit) byte
b = (b * 0x0202020202ULL & 0x010884422010ULL) % 1023;

如果要在32位int上执行这个操作,只需反转每个字节的比特数,并反转字节的顺序,也就是:


unsigned int toReverse;
unsigned int reversed;
unsigned char inByte0 = (toReverse & 0xFF);
unsigned char inByte1 = (toReverse & 0xFF00) >> 8;
unsigned char inByte2 = (toReverse & 0xFF0000) >> 16;
unsigned char inByte3 = (toReverse & 0xFF000000) >> 24;
reversed = (reverseBits(inByte0) << 24) | (reverseBits(inByte1) << 16) | (reverseBits(inByte2) << 8) | (reverseBits(inByte3);


结果

我确定了两个最有前途的解决方案,查找表和按位和(第一个),测试机是一台配备4GB DDR2-800和Core 2 Duo T7500 @ 2.4 GHz,4MB二级高速缓存的笔记本电脑;,YMMV,我在64位Linux上使用了gcc 4.3.2,OpenMP(和GCC绑定)用于高分辨率计时器。

reverse.c


#include <stdlib.h>
#include <stdio.h>
#include <omp.h>

unsigned int
reverse(register unsigned int x)
{
 x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
 x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2));
 x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4));
 x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8));
 return((x >> 16) | (x << 16));

}

int main()
{
 unsigned int *ints = malloc(100000000*sizeof(unsigned int));
 unsigned int *ints2 = malloc(100000000*sizeof(unsigned int));
 for(unsigned int i = 0; i < 100000000; i++)
 ints[i] = rand();

 unsigned int *inptr = ints;
 unsigned int *outptr = ints2;
 unsigned int *endptr = ints + 100000000;
 // Starting the time measurement
 double start = omp_get_wtime();
 // Computations to be measured
 while(inptr != endptr)
 {
 (*outptr) = reverse(*inptr);
 inptr++;
 outptr++;
 }
 // Measuring the elapsed time
 double end = omp_get_wtime();
 // Time calculation (in seconds)
 printf("Time: %f secondsn", end-start);

 free(ints);
 free(ints2);

 return 0;
}

reverse_lookup.c


#include <stdlib.h>
#include <stdio.h>
#include <omp.h>

static const unsigned char BitReverseTable256[] = 
{
 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
};

int main()
{
 unsigned int *ints = malloc(100000000*sizeof(unsigned int));
 unsigned int *ints2 = malloc(100000000*sizeof(unsigned int));
 for(unsigned int i = 0; i < 100000000; i++)
 ints[i] = rand();

 unsigned int *inptr = ints;
 unsigned int *outptr = ints2;
 unsigned int *endptr = ints + 100000000;
 // Starting the time measurement
 double start = omp_get_wtime();
 // Computations to be measured
 while(inptr != endptr)
 {
 unsigned int in = *inptr; 

 // Option 1:
 //*outptr = (BitReverseTable256[in & 0xff] << 24) | 
 // (BitReverseTable256[(in >> 8) & 0xff] << 16) | 
 // (BitReverseTable256[(in >> 16) & 0xff] << 8) |
 // (BitReverseTable256[(in >> 24) & 0xff]);

 // Option 2:
 unsigned char * p = (unsigned char *) &(*inptr);
 unsigned char * q = (unsigned char *) &(*outptr);
 q[3] = BitReverseTable256[p[0]]; 
 q[2] = BitReverseTable256[p[1]]; 
 q[1] = BitReverseTable256[p[2]]; 
 q[0] = BitReverseTable256[p[3]];

 inptr++;
 outptr++;
 }
 // Measuring the elapsed time
 double end = omp_get_wtime();
 // Time calculation (in seconds)
 printf("Time: %f secondsn", end-start);

 free(ints);
 free(ints2);

 return 0;
}

我尝试了两种不同的优化方法,每个级别运行3个试验,每个试验反转1亿随机无符号,对于查找表选项,我尝试了在按位黑客页面上给出的两个方案(选项1和2 ),下面显示了结果。

按位和


mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -o reverse reverse.c
mrj10@mjlap:~/code$ ./reverse
Time: 2.000593 seconds
mrj10@mjlap:~/code$ ./reverse
Time: 1.938893 seconds
mrj10@mjlap:~/code$ ./reverse
Time: 1.936365 seconds
mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -O2 -o reverse reverse.c
mrj10@mjlap:~/code$ ./reverse
Time: 0.942709 seconds
mrj10@mjlap:~/code$ ./reverse
Time: 0.991104 seconds
mrj10@mjlap:~/code$ ./reverse
Time: 0.947203 seconds
mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -O3 -o reverse reverse.c
mrj10@mjlap:~/code$ ./reverse
Time: 0.922639 seconds
mrj10@mjlap:~/code$ ./reverse
Time: 0.892372 seconds
mrj10@mjlap:~/code$ ./reverse
Time: 0.891688 seconds

查找表(选项1 )


mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -o reverse_lookup reverse_lookup.c
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 1.201127 seconds 
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 1.196129 seconds 
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 1.235972 seconds 
mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -O2 -o reverse_lookup reverse_lookup.c
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 0.633042 seconds 
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 0.655880 seconds 
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 0.633390 seconds 
mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -O3 -o reverse_lookup reverse_lookup.c
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 0.652322 seconds 
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 0.631739 seconds 
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 0.652431 seconds 

查找表(选项2 )


mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -o reverse_lookup reverse_lookup.c
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 1.671537 seconds
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 1.688173 seconds
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 1.664662 seconds
mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -O2 -o reverse_lookup reverse_lookup.c
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 1.049851 seconds
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 1.048403 seconds
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 1.085086 seconds
mrj10@mjlap:~/code$ gcc -fopenmp -std=c99 -O3 -o reverse_lookup reverse_lookup.c
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 1.082223 seconds
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 1.053431 seconds
mrj10@mjlap:~/code$ ./reverse_lookup
Time: 1.081224 seconds

结束语

如果你关心性能,请使用查找表,选项1(字节寻址速度慢得令人惊讶)。如果你需要从系统中挤出每个字节的内存(如果你关心位反转的性能你需要这样做),那么bit-AND方法的优化版本也不会太糟糕。

提醒

是的,我知道基准代码是一个完全的hack,我了解的内容:

  • 我没有访问ICC的权限,这更快。
  • 对于具有大型L1D的一些现代微体系结构,64K查找表可能表现良好。
  • -mtune=native没有为-o2/-o3 (ld重定义错误)工作,所以,我不相信生成的代码对我的微体系结构有所调优,
  • 使用SSE可能让它更快。
  • 这是在-O3上为选项1生成的代码GCC,所以可以查看它:

32位


.L3:
movl (%r12,%rsi), %ecx
movzbl %cl, %eax
movzbl BitReverseTable256(%rax), %edx
movl %ecx, %eax
shrl $24, %eax
mov %eax, %eax
movzbl BitReverseTable256(%rax), %eax
sall $24, %edx
orl %eax, %edx
movzbl %ch, %eax
shrl $16, %ecx
movzbl BitReverseTable256(%rax), %eax
movzbl %cl, %ecx
sall $16, %eax
orl %eax, %edx
movzbl BitReverseTable256(%rcx), %eax
sall $8, %eax
orl %eax, %edx
movl %edx, (%r13,%rsi)
addq $4, %rsi
cmpq $400000000, %rsi
jne .L3

程序集代码显示在(对于前一种情况,一次2 32位int的反转位)下面:


.L3:
movq (%r12,%rsi), %rdx
movq %rdx, %rax
shrq $24, %rax
andl $255, %eax
movzbl BitReverseTable256(%rax), %ecx
movzbq %dl,%rax
movzbl BitReverseTable256(%rax), %eax
salq $24, %rax
orq %rax, %rcx
movq %rdx, %rax
shrq $56, %rax
movzbl BitReverseTable256(%rax), %eax
salq $32, %rax
orq %rax, %rcx
movzbl %dh, %eax
shrq $16, %rdx
movzbl BitReverseTable256(%rax), %eax
salq $16, %rax
orq %rax, %rcx
movzbq %dl,%rax
shrq $16, %rdx
movzbl BitReverseTable256(%rax), %eax
salq $8, %rax
orq %rax, %rcx
movzbq %dl,%rax
shrq $8, %rdx
movzbl BitReverseTable256(%rax), %eax
salq $56, %rax
orq %rax, %rcx
movzbq %dl,%rax
shrq $8, %rdx
movzbl BitReverseTable256(%rax), %eax
andl $255, %edx
salq $48, %rax
orq %rax, %rcx
movzbl BitReverseTable256(%rdx), %eax
salq $40, %rax
orq %rax, %rcx
movq %rcx, (%r13,%rsi)
addq $8, %rsi
cmpq $400000000, %rsi
jne .L3

这个帖子引起了我的注意,因为它涉及到一个简单的问题,需要很多工作甚至( CPU周期) 现代cpu。 有一天,我也站在那里,有同样的¤#%"δ #"问题。 我不得不翻转数百万字节。 但是我知道我所有的目标系统都是现代的英特尔,所以让我们开始优化到极致 !

所以我使用了Matt对j 代码的查找作为基础。 我正在测试的系统是一个定制的haswell 4700 eq 。

对j bitflipping 400 000 000字节的查询: 大约 0.272秒左右。

然后我继续,想看看英特尔ISPC编译器可以 vectorise reverse.c. 算法

我不会生你在这里和我发现自从我试图帮助编译器找到很多东西,总之我最终的性能在 0.15秒 bitflipp 400 000 000字节。 这是大大减少,但对于我的应用程序仍然是缓慢的方式。

所以人们让我展示了世界上最快速的基于英特尔的bitflipper 。 时钟位于:

bitflip 400000000字节的时间: 0.050 082秒 !


//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 ("rnData in(start):rn");
 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 ("rn");
 }

 printf ("rnNumber of 32-byte chunks to convert: %drn",(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 ("rnData out:rn");
 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 ("rn");
 }
 printf("rnrnTime to bitflip %d bytes: %f secondsrnrn",NUM_DATA_BYTES, end_time-start_time);

//return with no errors
 return 0;
}

pritf debuging的。

以下是主力:


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字节,然后屏蔽贪吃蛇。 高的nibble被 4左右移动。 然后我使用vpshufb和 ymm4/ymm3作为查找表。 我可以使用一个查找表但我必须左移位之前打鼾又轻咬在一起。

有更快速的方法来翻转比特。 但是我绑定到了单线和 CPU,所以这是我能达到最快的速度。 你能做一个更快的版本?

请不要对使用 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

这里有一个递归函数来解决它,(注意我已经使用了无符号整数,所以,它可以工作到sizeof (无符号整型))*8位。

递归函数需要2个参数-需要反转位的值和值中的位数。


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%xn", num, reversedNum);

 num = 0xabcd;
 reversedNum = reverse_bits_recursive(num, 16);
 printf ("Bit Reversal Input = 0x%x Output = 0x%xn", num, reversedNum);

 num = 0x123456;
 reversedNum = reverse_bits_recursive(num, 24);
 printf ("Bit Reversal Input = 0x%x Output = 0x%xn", num, reversedNum);

 num = 0x11223344;
 reversedNum = reverse_bits_recursive(num,32);
 printf ("Bit Reversal Input = 0x%x Output = 0x%xn", 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

假设你有一个位数组,那么该如何: 1.从MSB开始,将push到一个堆栈,2.从该堆栈弹出位到另一个数组(如果你想节省空间,则是相同的数组),将第一个弹出位置于MSB中,然后从那里继续执行。


Stack stack = new Stack();
Bit[] bits = new Bit[] { 0, 0, 1, 0, 0, 0, 0, 0 };

for (int i = 0; i < bits.Length; i++) 
{
 stack.push(bits[i]);
}

for (int i = 0; i < bits.Length; i++)
{
 bits[i] = stack.pop();
}

这肯定不是像Matt这样的答案,但希望它仍然有用。


 unsigned int reverse(unsigned int t)
 {
 size_t n = t;//store in 64 bit number for call to BSWAP
 __asm__("BSWAP %0" :"=r"(n) :"0"(n));
 n>> = ((sizeof(size_t) - sizeof(unsigned int)) * 8);
 n = ((n & 0xaaaaaaaa)>> 1) | ((n & 0x55555555) <<1);
 n = ((n & 0xcccccccc)>> 2) | ((n & 0x33333333) <<2);
 n = ((n & 0xf0f0f0f0)>> 4) | ((n & 0x0f0f0f0f) <<4);
 return n;
 }

这是完全相同的想法最好的马特算法除了有这个小指令称为BSWAP互换的字节( 不是位) 64位 号码。 所以b7,b6,b5,b4,b3,b2,b1,b0变得b0,b1,b2,b3,b4,b5,b6,b7.因为我们正在与 32位 数量我们需要转变我们byte-swapped下来 32比特数。 这就让我们有了交换每个字节的8位的任务,这就是 ! 我们已经完成了。

计时:在我的机器上,matt的算法在 ~0.52 秒内运行。 每次试用时我的跑步时间大约为 0.42秒。 20%的速度不错我认为。

如果你担心的可用性指令 BSWAP 维基百科列出指令BSWAP添加与 80846 1989出来。 应该注意的是,维基百科也指出,这个指令只适用于 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 & 0xaaaaaaaa)>> 1) | ((n & 0x55555555) <<1);
 n = ((n & 0xcccccccc)>> 2) | ((n & 0x33333333) <<2);
 n = ((n & 0xf0f0f0f0)>> 4) | ((n & 0x0f0f0f0f) <<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) right-shift将被完全移除。 注意,GCC至少不能删除BSWAP和 right-shift,如果通过 sizeof(char)

我不确定它是否最有效,但是应该可以:


//returns n rotated right by b bits
int rotRight(int n, int b)
{
 if(b >= 0)
 b = b%(8*sizeof(int));
 else
 b = 8*sizeof(int) - (-b)%(8*sizeof(int));
 return (n >>> b) | (n << (8*sizeof(int) - b));
}

//returns n rotated left by b bits
int rotLeft(int n, int b)
{
 if(b >= 0)
 b = b%(8*sizeof(int));
 else
 b = 8*sizeof(int) - (-b)%(8*sizeof(int));
 return (n << b) | (n >>> (8*sizeof(int) - b));
}

更新:增加了对负"b"值的支持。

注意:这个答案是以早期版本的问题为基础,不正确地要求位旋转,即使不是这个问题。

当然,bit-twiddling攻击的明显来源在这里: http://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious

实现低内存和最快的实现。


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;
 }

泛型

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: %dn", x);

 // extract bit on the right, from LSB
 y = num & (1 << i);
 y = y >> i;
 printf("y: %dn", y);

 var = var | (x << i); // apply x
 var = var | (y << p); // apply y
 }

 printf("new: 0x%xn", new);

你可能需要使用标准模板库,它可能比上面提到的代码慢,然而我更清楚,这更容易理解。


 #include<bitset>
 #include<iostream>


 template<size_t N>
 const std::bitset<N> reverse(const std::bitset<N>& ordered)
 {
 std::bitset<N> reversed;
 for(size_t i = 0, j = N - 1; i < N; ++i, --j)
 reversed[j] = ordered[i];
 return reversed;
 };


 // test the function
 int main()
 {
 unsigned long num; 
 const size_t N = sizeof(num)*8;

 std::cin >> num;
 std::cout << std::showbase << std::hex;
 std::cout << "ordered = " << num << std::endl;
 std::cout << "reversed = " << reverse<N>(num).to_ulong() << std::endl;
 std::cout << "double_reversed = " << reverse<N>(reverse<N>(num)).to_ulong() << std::endl; 
 }

...