如何使用最有效的算法来实现以下转换：
0010 0000 => 0000 0100
转换是从高位到低位到低位到高位。所有位必须被反转，也就是说，这不是字节序交换。
在C语言中高效地实现比特反转算法（从最高位到最低位到从最低位到最高位）。
266
- green_t
8
6我觉得你的意思是“反转”，而不是“旋转”。 - Juliano
3大多数ARM处理器都有内置的操作来完成此操作。但是ARM Cortex-M0没有，我发现使用逐字节表格交换位是最快的方法。 - starblue
3请查看Sean Eron Anderson的位操作技巧。 - jww
2请定义“最好”。 - Lee Taylor
1为什么这个被关闭了，最好的定义应该是最快的方式... - Quonux
显示剩余3条评论
28个回答
521
注意：以下所有算法均使用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上执行此操作，只需反转每个字节中的位，并反转字节的顺序。 即：
如果您要在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 L2缓存的笔记本电脑；实际情况可能有所不同。我在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汇编语言；以下是GCC在选项1上生成的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 位 int 类型的位，还是实际上在一半的 64 位值中翻转位，性能几乎相同。下面显示了汇编代码（用于前一种情况，即一次反转两个 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
- Matt J
15
3-1 是因为这篇文章太详细和周到了。开玩笑的，+1。 - mpen
12这是一个有趣的练习，但并不是特别充实。如果没有其他收获的话，我希望这个过程对其他想要做出更有成就感的人有所裨益 :) - Matt J
6天啊！我想我已经找到了可能是真正的样本。我需要查阅我的文件并进行进一步的研究，但直觉告诉我（上帝保佑我），这是迄今为止 Stack Overflow 给出的最好、最全面和最有用的答案。即使 John Skeet 看到也会既惊讶又印象深刻！ - zeboidlund
4请注意，微基准测试（在其他许多缺陷中之一）的一个特别缺陷是它往往人为地偏向于查找表解决方案。由于基准测试正在循环执行一个操作，所以通常会发现使用一个刚好适配到L1缓存的查找表最快，因为每次都能够完全命中L1，而根本没有任何缓存压力。在实际用例中，该操作通常会与引起一定缓存压力的其他操作交错进行。一次RAM缺失可能比平时慢10倍或100倍，但在基准测试中被忽略了。 - BeeOnRope
3简译：如果两个解决方案相似，我通常会选择非LUT解决方案（或者较小的LUT），因为LUT在现实世界中可能会产生严重影响。更好的方法是针对每个解决方案进行“现场”基准测试-即在实际使用大型应用程序并具有真实输入的位置。当然，我们并不总是有时间这样做，也不总是知道真实输入是什么。 - BeeOnRope
显示剩余10条评论
93
这个帖子引起了我的关注，因为它涉及到一个简单的问题，即使对于现代CPU来说，需要大量的工作（CPU周期）来解决。有一天，我也面临着同样的问题。我不得不翻转数百万字节。然而，我知道我所有的目标系统都是基于现代英特尔处理器的，所以让我们开始极限优化吧！
因此，我使用Matt J的查找代码作为基础。我要进行基准测试的系统是i7 Haswell 4700eq。
Matt J的位翻转400,000,000字节：约0.272秒。
然后，我试图看看英特尔的ISPC编译器是否可以向量化reverse.c中的算术运算。
我不想在这里详细说明我的发现，因为我尽了很多努力帮助编译器找到东西，无论如何，最终我得到的性能是大约0.15秒来翻转400,000,000字节。虽然已经有了很大的提高，但对于我的应用程序来说，仍然太慢了...
所以，让我介绍世界上最快的基于英特尔的位翻转器。计时结果为：
翻转400,000,000字节的时间：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作为查找表。我本可以使用单个查找表，但那样就必须在将半字节进行OR运算之前左移。
有更快的翻转位的方法，但我只能使用单个线程和CPU，所以这是我能实现的最快速度。你能制作一个更快的版本吗？
请不要评论使用Intel C/C++编译器内置命令的事情...
- Anders Cedronius
14
2你应该得到比这更多的赞。我知道这可以用
pshub 做到，因为最好的 popcount 也是用它完成的！如果不是因为你，我会在这里写它的。好极了。 - Iwillnotexist Idonotexist3谢谢！“popcnt”是我另一个喜欢的主题。请查看我的BMI2版本：result = __tzcnt_u64（〜_pext_u64（data [i]，data [i]））; - Anders Cedronius
3将asm文件命名为：bitflip_asm.s
然后执行：yasm -f elf64 bitflip_asm.s
将c文件命名为：bitflip.c
然后执行：g++ -fopenmp bitflip.c bitflip_asm.o -o bitflip - Anders Cedronius
5英特尔处理器的执行单元
popcnt、tzcnt 和 pext 都在端口 1 上。因此，每个 pext 或 tzcnt 都会消耗一个 popcnt 的吞吐量。如果你的数据在 L1D 缓存中是热数据，那么在英特尔处理器上用 AVX2 pshufb 是最快的计算数组的 popcount 方法。（Ryzen 每个时钟有 4 个 popcnt 吞吐量，所以这可能是最优的选择，但 Bulldozer 系列每 4 个时钟只有一个 popcnt r64,r64 吞吐量 … http://agner.org/optimize/）。 - Peter Cordes6我自己使用基本内置函数版本。但是当我回答问题时，我发布了我所拥有的内容，并且从之前的帖子中知道，只要我写汇编语言，一个聪明的家伙就会指出我应该改用基本内置函数。在开发时，我首先编写汇编语言版本，然后，当我喜欢结果时，我会转向使用基本内置函数。那就是我的方式。我只是碰巧在我只有我的“测试”汇编版本时发布了我的答案。 - Anders Cedronius
显示剩余9条评论
18
对于热爱递归的人，这是另一种解决方案。
思路很简单。 将输入分成两半并交换这两半，然后继续进行此操作，直到达到单个位。
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
- Dennis Mathews
1
2这种方法在24位的例子（第3个）上无法正常工作吗？我对C和位运算符不是很熟悉，但从您对该方法的解释中，我猜测24->12->6->3（3位不均匀分割）。由于
numBits是int类型，当您将3除以2用于函数参数时，它会向下舍入为1？ - Brennan17
好吧，这肯定不像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指令的可用性，请参考维基百科，列出了添加了80846的BSWAP指令，该指令于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 & 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中，如果传递sizeof(char)，则无法删除BSWAP和右移操作。
- SirGuy
5
2根据英特尔指令集参考手册第2A卷(http://www.intel.com/content/www/us/en/processors/architectures-software-developer-manuals.html?iid=tech_vt_tech+64-32_manuals)，有两个BSWAP指令：BSWAP r32（适用于32位寄存器），编码为0F C8+rd，以及BSWAP r64（适用于64位寄存器），编码为REX.W + 0F C8+rd。 - Nubok
你说它可以这样使用："n = reverse(n, sizeof(size_t));//reverse 64 bits"，但是除非所有的常量都扩展到64位，否则它只会给出32位的结果，然后它才能正常工作。 - rajkosto
好的？我只是想说，如果你想让这个在64位值上工作，你必须扩展你的字面量（例如，它们应该是0xf0f0f0f0f0f0f0f0ull），否则结果的高32位将全部为0。 - rajkosto
@rajkosto 啊，我误解了你的第一条评论，现在我已经修复了。 - SirGuy
16
Anders Cedronius的回答为那些拥有支持AVX2的x86 CPU的人提供了一个很好的解决方案。对于没有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展示了一些巧妙地反转位的方法，这些方法需要的操作比传统的二进制分区算法少得多，令人惊讶。其中一种用于32位操作数的算法，在TAOCP中找不到，可以在Hacker's Delight网站上的此文档中找到。请注意保留HTML标签。
/* 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上，使用自动向量化代码，100 million个
uint32_t单词在0.070秒内通过brev_classic()进行了位反转，并且在0.068秒内使用brev_knuth()完成。我注意确保我的基准测试不受系统内存带宽限制。- njuffa
1
3我假设你所说的“很多神奇数字”主要是指
brev_knuth()函数？Hacker's Delight中PDF文件中的归属表明这些数字直接来自于Knuth。我无法声称已完全理解TAOCP中基础设计原则的描述，也无法说明这些常数是如何派生出来的，或者如何为任意字长派生常数和移位因子。 - njuffa10
这不是人类的工作！...但对于机器来说是完美的
现在是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指令生成艺术品般优美的代码，并在处理约10亿个reverse()时运行11秒。每个reverse()大约需要10纳秒，假设CPU周期为2 GHz，则需要0.5纳秒的CPU周期，这使我们达到了完美的20个CPU周期。
- 您可以在访问一次RAM以获取单个大数组的时间内容纳10个reverse()！
- 您可以在访问L2高速缓存LUT两次的时间内容纳1个reverse()。
注意：此样例代码应作为一个不错的基准测试，但随着编译器越来越聪明，能够将main()优化为仅printf最终结果而非真正计算任何内容，它最终会开始显得过时。但是现在它可以展示reverse()。
- user2875414
4
1“位反转非常常见...” 我不知道这一点。我几乎每天都在处理位级数据的代码中工作，但我无法回想起曾经有过这个特定需求的情况。你在什么场景下需要它呢？- 不是说解决这个问题本身不有趣。 - 500 - Internal Server Error
@500-服务器内部错误 我在使用快速、简洁的数据结构进行语法推理时，经常需要使用此函数。将普通的二叉树编码为位数组会以“大端”顺序推断语法。但是，如果您通过位反转置换来交换节点构建一棵树（位数组），则学习到的语法字符串将是“小端”，从而实现更好的泛化。这种情况在高效FFT中也经常出现：请参见https://en.wikipedia.org/wiki/Bit-reversal_permutation。 - user2875414
1谢谢，我不知怎么地直觉到你的答案中可能涉及FFT :) - 500 - Internal Server Error
为什么只有20个周期？是哪种架构？这对未来所有超宽VLIW架构都适用吗，直到人类和我们的后代灭绝？只是问题，没有答案...再次被踩到地狱。 - Quonux
10
使用本地的ARM指令“rbit”可以在1个CPU周期和1个额外的CPU寄存器中完成，无法被超越。
- metalogic
8
假设您有一组位数组，请按照以下步骤操作： 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();
}
- Frederick The Fool
2
4这句话让我笑了 :) 我很想看到这个C#解决方案与我上面概述的优化C语言解决方案之一的基准测试比较。 - Matt J
LOL... 但是嘿！“最佳算法”中的形容词“最佳”是一件相当主观的事情:D - Frederick The Fool
5
实现低内存占用和最快速度。
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;
}
- Aung
4
我很好奇显然的原始旋转会有多快。在我的机器上（i7@2600），1500150000次迭代的平均值为
优点：所需内存很少，代码也很简单。我想说它也不是很大。对于任何输入，所需的时间是可预测且恒定的（128个算术SHIFT操作+64个逻辑AND操作+64个逻辑OR操作）。
我与@Matt J获得的最佳时间进行了比较-他的回答被接受。如果我正确地阅读他的回答，那么他得到的最佳时间是
我使用的代码片段如下:
27.28纳秒（使用131071个64位整数的随机集合）。优点：所需内存很少，代码也很简单。我想说它也不是很大。对于任何输入，所需的时间是可预测且恒定的（128个算术SHIFT操作+64个逻辑AND操作+64个逻辑OR操作）。
我与@Matt J获得的最佳时间进行了比较-他的回答被接受。如果我正确地阅读他的回答，那么他得到的最佳时间是
0.631739秒，用于1,000,000次迭代，这导致每次旋转的平均时间为631 ns。我使用的代码片段如下:
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);
}
- marian adam
2
@老程序员，我不确定我理解你的问题。 - marian adam
感谢您注意到这个错误，我已经修复了提供的代码示例。 - marian adam
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接