首页   技术笔记   网址导航   Json在线解析   二维码   Ip地址查询   在线流程图  
新用户注册 | 会员登录
当前位置:  开发笔记 > 编程语言 > 正文

C中用于比特反转的最有效算法(从MSB-> LSB到LSB-> MSB)

作者：有风吹过best | 2023-08-28 08:54
如何解决《C中用于比特反转的最有效算法(从MSB->LSB到LSB->MSB)》经验，为你挑选了10个好方法。

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

0010 0000 => 0000 0100

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



1> Matt J..：

注意:下面的所有算法都是用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);

结果

我对两个最有前途的解决方案,查找表和按位AND(第一个)进行了基准测试.该测试机是一台配备4GB DDR2-800和Core 2 Duo T7500 @ 2.4GHz,4MB L2 Cache的笔记本电脑; 因人而异.我在64位Linux上使用了gcc 4.3.2.OpenMP(和GCC绑定)用于高分辨率计时器.

reverse.c

#include 
#include 
#include 

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 
#include 
#include 

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亿次unsigned ints.对于查找表选项,我尝试了在按位黑客页面上给出的两个方案(选项1和2).结果如下所示.

按位AND

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方法的优化版本也不会太破旧.

警告

是的,我知道基准代码是一个完整的黑客.关于如何改进它的建议非常受欢迎.我所知道的事情:

我无法访问ICC.这可能会更快(如果你可以测试一下,请回复评论).

对于具有大型L1D的一些现代微体系结构,64K查找表可能表现良好.

-mtune = native对-O2/-O3不起作用(ld引发一些疯狂的符号重定义错误),所以我不相信生成的代码会针对我的微体系结构进行调整.

使用SSE可能有一种方法可以更快地完成此操作.我不知道如何,但是通过快速复制,压缩按位AND和调配指令,必须有一些东西.

我知道只有足够的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位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

这是一项有趣的练习,如果不是所有的充实.如果不出意外的话,我希望看到这个过程对其他人来说是有建设性的,他们可能想要更有价值的东西:)
天哪!我想我已经找到了...很可能......一个真正的特工.我将不得不查阅我的文档,并做进一步的研究,但有些东西告诉我(上帝,帮助我),这是迄今为止Stack Overflow迄今为止最伟大,最彻底和最有用的答案.即使是John Skeet也会感到震惊和印象深刻!
-1为过于详细和透彻的帖子。j / k。+1。
请记住，微基准测试的一个特殊缺陷（包括许多其他缺陷）是它倾向于人为地偏爱基于查找表的解决方案。由于基准测试是在循环中重复一次操作，因此通常会发现使用仅适合L1的查找表是最快的，因为每次都不会出现L1缓存，因此所有内容都会每次都到达L1。在实际使用情况下，该操作通常会与其他操作交织在一起，从而导致某些缓存压力。错过RAM所花费的时间可能比平时长10或100倍，但这在基准测试中被忽略。
结果是,如果两个解决方案接近,我经常选择非LUT解决方案(或具有较小LUT的解决方案),因为LUT的真实世界影响可能很严重.更好的方法是"原位"对每个解决方案进行基准测试 - 它实际上在较大的应用程序中使用,具有真实的输入.当然,我们并不总是有时间,我们并不总是知道什么是现实的输入.

2> Anders Cedro..：

这个线程引起了我的注意,因为它处理一个简单的问题,即使对于现代CPU也需要大量的工作(CPU周期).有一天,我也站在那里,遇到同样的¤#%"#"问题.我不得不翻转数百万字节.但是我知道我所有的目标系统都是现代的基于英特尔的,所以让我们开始优化到极致!

所以我用Matt J的查找代码作为基础.我正在进行基准测试的系统是i7 haswell 4700eq.

Matt J的查找位翻转400 000 000字节:大约0.272秒.

然后我继续尝试看看英特尔的ISPC编译器是否可以在反向转换算法中使用算法.

因为我尝试了很多东西来帮助编译器找到东西,所以我最终得到了大约0.15秒的性能来bitflip 400 000 000字节.这是一个很大的减少,但对于我的应用程序仍然太慢..

所以人们让我展示了世界上最快的基于英特尔的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 
#include 
#include 
#include 

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++编译器内在等效命令发表评论......

英特尔CPU在端口1上都有`popcnt`,`tzcnt`和`pext`的执行单元.因此每个`pext`或`tzcnt`都会让你失去吞吐量.如果您的数据在L1D缓存中很热,那么在Intel CPU上弹出阵列的最快方法是使用AVX2 pshufb.(Ryzen每时钟有4个'popcnt`吞吐量,所以这可能是最佳的,但Bulldozer系列每4个时钟有一个`popcnt r64,r64`吞吐量...... http://agner.org/optimize/).
谢谢!'popcnt'是我最喜欢的主题;)查看我的BMI2版本:result = __ tzcnt_u64(~_pext_u64(data [i],data [i]));
将asm文件命名为:bitflip_asm.s then:yasm -f elf64 bitflip_asm.s将c文件命名为:bitflip.c then:g ++ -fopenmp bitflip.c bitflip_asm.o -o bitflip就是这样.
我自己使用的是内在版本.然而,当我回答时,我发布了我所拥有的内容,并且从之前的帖子中我知道,一旦我编写汇编程序,一个聪明的aleck总是指出我应该在内在函数中完成它.当我开发时,我首先编写汇编程序,当我喜欢结果时,我转向内在函数..那就是我......当我只有我的'test'汇编程序版本时,我恰好发布了我的答案.
你应该得到比这更多的FAR.我知道这应该可以用`pshub`来实现,因为毕竟最好的popcount也用它完成了!如果没有你,我会把它写在这里.荣誉.
哈!对于那个,我独立地想出类似的东西,因为我注意到`pext(x,x)`在最后几位连续收集所有(不连续的),因此可以作为`return 64-lzcnt(pext)来完成(X,X))`.不可否认,`return tzcnt(~pext(x,x))`更整齐,更短.
我有一个疯狂的想法,即通过将popcnt与BMI2和AVX2交错来最大化popcnt,理论上可以并行使用CPU中的所有算术单元.然而,内存太慢而且测试的结果只是一种新的popcnting方式:) ..所以你说对了popcnt你没有必要做任何花哨的技巧.http://stackoverflow.com/questions/27473882/fastest-64-bit-population-count-hamming-weight
如果你想要GCC,那么删除"using namespace std;" 和extern"C"+括号.那么:gcc -std = c99 -fopenmp bitflip.c bitflip_asm.o -o bitflip

3> Dennis Mathe..：

对于喜欢递归的人来说,这是另一种解决方案.

这个想法很简单.将输入分为两半并交换两半,继续直到达到单个位.

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



4> SirGuy..：

那么这肯定不会像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 维基百科会将指令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).

根据英特尔指令集参考卷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.

5> njuffa..：

Anders Cedronius的回答为拥有支持AVX2的x86 CPU 的用户提供了一个很好的解决方案.对于没有AVX支持或非x86平台的x86平台,以下任一实现都应该可以正常工作.

第一个代码是经典二进制分区方法的一种变体,经编码以最大限度地利用在各种ARM处理器上有用的shift-plus-logic惯用法.此外,它使用动态掩码生成,这对于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上,使用自动矢量化代码,uint32_t在0.070秒内使用1亿个字位反转,使​​用brev_classic()0.068秒brev_knuth().我注意确保我的基准测试不受系统内存带宽的限制.



6> Frederick Th..：

假设你有一个位数组,那么: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();
}

这个让我微笑:)我很想看到这个C#解决方案的基准对照我在上面优化的C中概述的一个.

7> 小智..：

本机ARM指令"rbit"可以用1个cpu周期和1个额外的cpu寄存器来实现,不可能被击败.



8> 小智..：

这不是一个人的工作! ......但对于机器来说是完美的

这是2015年,也就是第一次提出这个问题的6年.编辑器从此成为我们的主人,而我们作为人类的工作只是为了帮助他们.那么将我们的意图用于机器的最佳方式是什么？

位反转是如此常见,以至于你不得不想知道为什么x86不断增长的ISA不包含一次性指令.

原因是:如果你给编译器提供真正简洁的意图,那么位反转应该只需要20个CPU周期.让我告诉你如何制作reverse()并使用它:

#include 
#include 

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指令提供图形质量的代码,运行时间为11秒,处理~10亿reverse()s.每个反向()大约10 ns,假设2 GHz,0.5 ns的CPU周期使我们处于甜蜜的20个CPU周期.

对于单个大型阵列,您可以在访问RAM一次所需的时间内安装10个reverse()!

您可以在两次访问L2缓存LUT所需的时间内调整1 reverse().

警告:这个示例代码应该在几年内作为一个不错的基准,但是一旦编译器足够聪明以优化main()以仅仅打印最终结果而不是真正计算任何东西,它最终将开始显示它的年龄.但是现在它可以展示reverse().



9> Anders Hanss..：

当然,这里有一个明显的尖端黑客来源:http: //graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious



10> 小智..：

我知道它不是C而是asm:

var1 dw 0f0f0
clc
     push ax
     push cx
     mov cx 16
loop1:
     shl var1
     shr ax
loop loop1
     pop ax
     pop cx

这适用于进位,因此您也可以保存标志

推荐阅读
devbox
有风吹过best
这个屌丝很懒，什么也没留下！
关注作者
Tags | 热门标签
RankList | 热门文章
DevBox开发工具箱 | 专业的在线开发工具网站    京公网安备 11010802040832号  |  京ICP备19059560号-6
Copyright © 1998 - 2020 DevBox.CN. All Rights Reserved devBox.cn 开发工具箱 版权所有