在C 中最有效的位反转算法（从MSB-> LSB到LSB-> MSB）
什么是最好的算法来实现以下内容：
0010 0000 => 0000 0100
转换是从MSB-> LSB到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 ，或者为了加快速度（假设您的L1数据缓存足够大）而对内存进行权衡，并使用64K条目查找表一次反转16位。
其他
简单
unsigned int v; // input bits to be reversed unsigned int r = v & 1; // 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.4GHz，4MB二级缓存; 因人而异。 我在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 seconds\n", 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 seconds\n", 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 （字节寻址速度不会太慢）。 如果你需要从系统中挤出每一个字节的内存（如果你关心位反转的性能，你可能会这么做），按位与方法的优化版本也不是太简单。
警告
是的，我知道基准代码是一个完整的黑客。 如何改进它的建议是值得欢迎的。 我知道的事情：
- 我无法访问ICC。 这可能会更快（如果可以测试的话，请回复评论）。
- 一个64K的查找表可能在一些具有大的L1D的现代微体系结构上表现良好。
- -mtune = native不能用于-O2 / -O3（
ld因为一些疯狂的符号重定义错误而失败），所以我不相信为我的微架构调整了生成的代码。 - SSE可能会稍微加快一点。 我不知道如何，但快速复制，按位加上，并指示混纺，那里有一些东西。
- 我知道只有足够的x86程序集是危险的; 这里是在-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
编辑：我也尝试在我的机器上使用uint64_t的，看看是否有任何性能提升。 性能比32位要快10％左右，而且不管你是只用64位类型在一次32位整数上反转位，还是实际上是把位反转一半，位值。 汇编代码如下所示（对于前一种情况，一次反转2个32位整数）：
.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的查找代码作为基础。 我正在测试的系统是i7 haswell 4700eq。
马特J的查找翻转400000000字节：大约0.272秒。
然后，我继续尝试查看英特尔ISPC编译器是否可以在reverse.c中引导算法。
我不会因为我的调查结果而感到厌烦，因为我尝试了很多方法来帮助编译器找到东西，不管怎样，我最终的性能是在bitflipp 400 000 000字节左右。 这是一个伟大的减少，但对于我的应用程序，仍然是缓慢的方式..
所以人们让我介绍世界上最快的基于intel的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; }
pritf的调试..
这是主力：
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作为查找表。 我可以使用单个查找表，但是之后我必须先左移，然后再将这些小数点组合在一起。
还有更快的翻转位的方法。 但我必须单线程和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（unsigned int）* 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%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
假设你有一个位数组，那怎么样：1.从MSB开始，一个接一个地把数据压入堆栈。 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(); }
那么这当然不会像马特·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)情况，右移将被完全移除。 请注意，GCC至少无法删除BSWAP，如果传递sizeof(char) ，则右移。
Anders Cedronius的答案为那些具有支持AVX2的x86 CPU的人提供了一个很好的解决方案。 对于没有AVX支持或非x86平台的x86平台，以下任何一种实现都应该可以正常工作。
第一个代码是经典的二进制分区方法的一个变体，编码是为了最大限度地利用在各种ARM处理器上有用的移位加逻辑习语。 此外，它使用动态掩码生成，这可能对RISC处理器有益，否则需要多条指令来加载每个32位掩码值。 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展示了反转比特的巧妙方式，与传统的二进制分割算法相比，有点令人吃惊的是需要更少的操作。 一个这样的32位操作数的算法，在TAOCP中找不到，在Hacker's Delight网站上的这个文档中被显示。
/* 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秒内brev_classic() 1亿uin32_t单词uin32_t ，在brev_classic() 0.068秒。 我注意确保我的基准不受系统内存带宽的限制。
当然，在这里显而易见的来源是： http : //graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious
我知道这不是C但是ASM：
var1 dw 0f0f0 clc push ax push cx mov cx 16 loop1: shl var1 shr ax loop loop1 pop ax pop cx
这与进位位一起工作，所以你也可以保存标志
低内存和最快的执行。
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; }
您可能想要使用标准模板库。 它可能比上面提到的代码慢。 但是，在我看来，似乎更清晰，更容易理解。
#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; }
通用
C code. Using 1 byte input data num as example.
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);
How about the following:
uint reverseMSBToLSB32ui(uint input) { uint output = 0x00000000; uint toANDVar = 0; int places = 0; for (int i = 1; i < 32; i++) { places = (32 - i); toANDVar = (uint)(1 << places); output |= (uint)(input & (toANDVar)) >> places; } return output; }
Small and easy (though, 32 bit only).
I was curious how fast would be the obvious raw rotation. On my machine (i7@2600), the average for 1,500,150,000 iterations was 27.28 ns (over aa random set of 131,071 64-bit integers).
Advantages: the amount of memory needed is little and the code is simple. I would say it is not that large, either. The time required is predictable and constant for any input (128 arithmetic SHIFT operations + 64 logical AND operations + 64 logical OR operations).
I compared to the best time obtained by @Matt J – who has the accepted answer. If I read his answer correctly, the best he has got was 0.631739 seconds for 1,000,000 iterations, which leads to an average of 631 ns per rotation.
The code snippet I used is this one below:
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); }
This ain't no job for a human! … but perfect for a machine
This is 2015, 6 years from when this question was first asked. Compilers have since become our masters, and our job as humans is only to help them. So what's the best way to give our intentions to the machine?
Bit-reversal is so common that you have to wonder why the x86's ever growing ISA doesn't include an instruction to do it one go.
The reason: if you give your true concise intent to the compiler, bit reversal should only take ~20 CPU cycles . Let me show you how to craft reverse() and use it:
#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; }
Compiling this sample program with Clang version >= 3.6, -O3, -march=native (tested with Haswell), gives artwork-quality code using the new AVX2 instructions, with a runtime of 11 seconds processing ~1 billion reverse()s. That's ~10 ns per reverse(), with .5 ns CPU cycle assuming 2 GHz puts us at the sweet 20 CPU cycles.
- You can fit 10 reverse()s in the time it takes to access RAM once for a single large array!
- You can fit 1 reverse() in the time it takes to access an L2 cache LUT twice.
Caveat: this sample code should hold as a decent benchmark for a few years, but it will eventually start to show its age once compilers are smart enough to optimize main() to just printf the final result instead of really computing anything. But for now it works in showcasing reverse().
Native ARM instruction "rbit" can do it with 1 cpu cycle and 1 extra cpu register, impossible to beat.
Well, this is basically the same as the first "reverse()" but it is 64 bit and only needs one immediate mask to be loaded from the instruction stream. GCC creates code without jumps, so this should be pretty fast.
#include <stdio.h> static unsigned long long swap64(unsigned long long val) { #define ZZZZ(x,s,m) (((x) >>(s)) & (m)) | (((x) & (m))<<(s)); /* val = (((val) >>16) & 0xFFFF0000FFFF) | (((val) & 0xFFFF0000FFFF)<<16); */ val = ZZZZ(val,32, 0x00000000FFFFFFFFull ); val = ZZZZ(val,16, 0x0000FFFF0000FFFFull ); val = ZZZZ(val,8, 0x00FF00FF00FF00FFull ); val = ZZZZ(val,4, 0x0F0F0F0F0F0F0F0Full ); val = ZZZZ(val,2, 0x3333333333333333ull ); val = ZZZZ(val,1, 0x5555555555555555ull ); return val; #undef ZZZZ } int main(void) { unsigned long long val, aaaa[16] = { 0xfedcba9876543210,0xedcba9876543210f,0xdcba9876543210fe,0xcba9876543210fed , 0xba9876543210fedc,0xa9876543210fedcb,0x9876543210fedcba,0x876543210fedcba9 , 0x76543210fedcba98,0x6543210fedcba987,0x543210fedcba9876,0x43210fedcba98765 , 0x3210fedcba987654,0x210fedcba9876543,0x10fedcba98765432,0x0fedcba987654321 }; unsigned iii; for (iii=0; iii < 16; iii++) { val = swap64 (aaaa[iii]); printf("A[]=%016llX Sw=%016llx\n", aaaa[iii], val); } return 0; }
I thought this is one of the simplest way to reverse the bit. please let me know if there is any flaw in this logic. basically in this logic, we check the value of the bit in position. set the bit if value is 1 on reversed position.
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; }
Bit reversal in pseudo code
source -> byte to be reversed b00101100 destination -> reversed, also needs to be of unsigned type so sign bit is not propogated down
copy into temp so original is unaffected, also needs to be of unsigned type so that sign bit is not shifted in automaticaly
bytecopy = b0010110
LOOP8: //do this 8 times test if bytecopy is < 0 (negative)
set bit8 (msb) of reversed = reversed | b10000000 else do not set bit8 shift bytecopy left 1 place bytecopy = bytecopy << 1 = b0101100 result shift result right 1 place reversed = reversed >> 1 = b00000000 8 times no then up^ LOOP8 8 times yes then done.
The Question asked is for reversing a byte (8 Bits of data)
typedef unsigned char byte; byte reverseByte(byte a) { int i; byte b = 0; for ( i = 0 ; i < 8 ; i ++) { b <<= 1; b |= ( (a & (1 << i)) >> i); } return b; }
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; }
I think the simplest method I know follows. MSB is input and LSB is 'reversed' output:
unsigned char rev(char MSB) { unsigned char LSB=0; // for output _FOR(i,0,8) { LSB= LSB << 1; if(MSB&1) LSB = LSB | 1; MSB= MSB >> 1; } return LSB; } // It works by rotating bytes in opposite directions. // Just repeat for each byte.
// Purpose: to reverse bits in an unsigned short integer // Input: an unsigned short integer whose bits are to be reversed // Output: an unsigned short integer with the reversed bits of the input one unsigned short ReverseBits( unsigned short a ) { // declare and initialize number of bits in the unsigned short integer const char num_bits = sizeof(a) * CHAR_BIT; // declare and initialize bitset representation of integer a bitset<num_bits> bitset_a(a); // declare and initialize bitset representation of integer b (0000000000000000) bitset<num_bits> bitset_b(0); // declare and initialize bitset representation of mask (0000000000000001) bitset<num_bits> mask(1); for ( char i = 0; i < num_bits; ++i ) { bitset_b = (bitset_b << 1) | bitset_a & mask; bitset_a >>= 1; } return (unsigned short) bitset_b.to_ulong(); } void PrintBits( unsigned short a ) { // declare and initialize bitset representation of a bitset<sizeof(a) * CHAR_BIT> bitset(a); // print out bits cout << bitset << endl; } // Testing the functionality of the code int main () { unsigned short a = 17, b; cout << "Original: "; PrintBits(a); b = ReverseBits( a ); cout << "Reversed: "; PrintBits(b); } // Output: Original: 0000000000010001 Reversed: 1000100000000000
This is for 32 bit, we need to change the size if we consider 8 bits. 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); }
// reading the input integer "num" in LSB->MSB order and storing in num_reverse in MSB->LSB order.
Another loop-based solution that exits quickly when the number is low (in C++ for multiple types)
template<class T> T reverse_bits(T in) { T bit = static_cast<T>(1) << (sizeof(T) * 8 - 1); T out; for (out = 0; bit && in; bit >>= 1, in >>= 1) { if (in & 1) { out |= bit; } } return out; }
or in C for an unsigned int
unsigned int reverse_bits(unsigned int in) { unsigned int bit = 1u << (sizeof(T) * 8 - 1); unsigned int out; for (out = 0; bit && in; bit >>= 1, in >>= 1) { if (in & 1) out |= bit; } return out; }
It seems that many other posts are concerned about speed (ie best = fastest). What about simplicity? 考虑：
char ReverseBits(char character) { char reversed_character = 0; for (int i = 0; i < 8; i++) { char ith_bit = (c & (1 << i)) >> i; reversed_character |= (ith_bit << (sizeof(char) - 1 - i)); } return reversed_character; }
and hope that clever compiler will optimise for you.
If you want to reverse a longer list of bits (containing sizeof(char) * n bits), you can use this function to get:
void ReverseNumber(char* number, int bit_count_in_number) { int bytes_occupied = bit_count_in_number / sizeof(char); // first reverse bytes for (int i = 0; i <= (bytes_occupied / 2); i++) { swap(long_number[i], long_number[n - i]); } // then reverse bits of each individual byte for (int i = 0; i < bytes_occupied; i++) { long_number[i] = ReverseBits(long_number[i]); } }
This would reverse [10000000, 10101010] into [01010101, 00000001].
My simple solution
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;
int bit_reverse(int w, int bits) { int r = 0; for (int i = 0; i < bits; i++) { int bit = (w & (1 << i)) >> i; r |= bit << (bits - i - 1); } return r; }
int main() { int n; scanf("%d", &n); while (n) { if (n & 1) printf("1"); else printf("0"); n >>= 1; } printf("\n"); } Output: 25 10011
