实现以下目标的最有效算法是:

0010 0000 => 0000 0100

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

评论

我认为适当的名称是按位运算。

我认为您的意思是反转,而不是轮换。

大多数ARM处理器对此都有内置的操作。 ARM Cortex-M0没有,我发现使用每字节表交换位是最快的方法。

另请参阅肖恩·埃隆·安德森(Sean Eron Anderson)的《 Bit Twiddling Hacks》。

请定义“最佳”

#1 楼

注意:以下所有算法均使用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条目查找表一次反转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 L2缓存; 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 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亿个随机unsigned ints进行了逆转。对于查找表选项,我尝试了按位hacks页面上给出的两种方案(选项1和2)。结果显示在下面。 >
查找表(选项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的查找表(字节寻址很慢)。如果您需要从系统中挤出内存的最后一个字节(并且您可能会关心位反转的性能),那么按位“与”方法的优化版本也不会太破旧。

注意事项


是的,我知道基准代码是一个完整的技巧。我们非常欢迎有关如何改进它的建议。我知道的事情:


我没有访问ICC的权限。这可能会更快(如果可以测试,请在评论中回复)。
在一些具有较大L1D的现代微体系结构上,64K查找表可能效果很好。 -O2 / -O3(ld炸毁了一些疯狂的符号重新定义错误),所以我不认为生成的代码针对我的微体系结构进行了调整。我不知道该怎么做,但是有了快速复制,按位AND打包以及指令繁琐的说明,那里肯定会有东西。
我只知道足够多的x86程序集会很危险。这是在-O3上为选项1生成的代码GCC,因此比我本人更了解的人可以查看一下:

32位

>编辑:我还尝试在计算机上使用uint64_t类型,以查看是否有任何性能提升。性能比32位快大约10%,并且无论您是一次使用64位类型一次反转两个32位int类型上的位,还是实际上反转了64个一半的位,性能几乎都相同位值。汇编代码如下所示(对于前一种情况,一次反转两种32位int类型的位):

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  


评论


-1为过于详细和透彻的帖子。 j / k。 +1。

– mpen
09年4月14日在7:02

这是一个有趣的练习,即使不是那么令人满意。如果没有别的,我希望看到这个过程对那些可能希望对一些更好的东西进行基准测试的人具有建设性:)

–马特J
09年4月14日在7:09

天哪!我想我已经发现...很可能是...一个真正的标本。我将不得不查阅我的文档,并做进一步的研究,但是有件事告诉我(上帝,救救我),这是到目前为止Stack Overflow迄今为止最伟大,最彻底和最有用的答案。甚至约翰·斯基特(John Skeet)都会感到震惊和震惊!

–zeboidlund
2012年5月5日在2:42

请记住,微基准测试的一个特殊缺陷(包括许多其他缺陷)是它倾向于人为地支持基于查找表的解决方案。由于基准测试是在循环中重复一次操作,因此通常会发现使用仅适合L1的查找表是最快的,因为每次都没有缓存压力,因此每次都会在L1中命中。在实际使用情况下,该操作通常会与其他导致某些缓存压力的操作交织在一起。错过RAM所花费的时间可能比平常长10或100倍,但这在基准测试中被忽略。

–BeeOnRope
15年8月20日在19:56

结果是,如果两个解决方案很接近,我经常会选择非LUT解决方案(或LUT较小的解决方案),因为LUT在现实世界中的影响可能很严重。更好的方法是“现场”对每个解决方案进行基准测试-在实际应用中,该解决方案实际用于大型应用程序中。当然,我们并不总是有时间这样做,我们也不总是知道什么是现实的输入。

–BeeOnRope
15年8月20日在19:58

#2 楼

这个线程引起了我的注意,因为它处理的是一个简单的问题,即使对于现代CPU来说,也需要大量的工作(CPU周期)。有一天,我也遇到了同样的¤#%“#”问题。我不得不翻转数百万个字节。但是我知道我所有的目标系统都是基于Intel的现代系统,所以让我们开始进行优化!!!我正在测试的系统是i7 haswell 4700eq。

Matt J的查找位翻转400000000字节:大约0.272秒。

然后我继续尝试看如果英特尔的ISPC编译器可以对向量进行反向量化处理。性能约为0.15秒,可翻转400000000字节。这是一个很大的减少,但是对于我的应用程序来说仍然太慢了。时钟在:

时间翻转400000000字节:0.050082秒!!!!!

// Bitflip using AVX2 - The fastest Intel based bitflip in the world!!
// Made by Anders Cedronius 2014 (anders.cedronius (you know what) gmail.com)

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

using namespace std;

#define DISPLAY_HEIGHT  4
#define DISPLAY_WIDTH   32
#define NUM_DATA_BYTES  400000000

// Constants (first we got the mask, then the high order nibble look up table and last we got the low order nibble lookup table)
__attribute__ ((aligned(32))) static unsigned char k1[32*3]={
        0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,0x0f,
        0x00,0x08,0x04,0x0c,0x02,0x0a,0x06,0x0e,0x01,0x09,0x05,0x0d,0x03,0x0b,0x07,0x0f,0x00,0x08,0x04,0x0c,0x02,0x0a,0x06,0x0e,0x01,0x09,0x05,0x0d,0x03,0x0b,0x07,0x0f,
        0x00,0x80,0x40,0xc0,0x20,0xa0,0x60,0xe0,0x10,0x90,0x50,0xd0,0x30,0xb0,0x70,0xf0,0x00,0x80,0x40,0xc0,0x20,0xa0,0x60,0xe0,0x10,0x90,0x50,0xd0,0x30,0xb0,0x70,0xf0
};

// The data to be bitflipped (+32 to avoid the quantization out of memory problem)
__attribute__ ((aligned(32))) static unsigned char data[NUM_DATA_BYTES+32]={};

extern "C" {
void bitflipbyte(unsigned char[],unsigned int,unsigned char[]);
}

int main()
{

    for(unsigned int i = 0; i < NUM_DATA_BYTES; i++)
    {
        data[i] = rand();
    }

    printf ("\r\nData in(start):\r\n");
    for (unsigned int j = 0; j < 4; j++)
    {
        for (unsigned int i = 0; i < DISPLAY_WIDTH; i++)
        {
            printf ("0x%02x,",data[i+(j*DISPLAY_WIDTH)]);
        }
        printf ("\r\n");
    }

    printf ("\r\nNumber of 32-byte chunks to convert: %d\r\n",(unsigned int)ceil(NUM_DATA_BYTES/32.0));

    double start_time = omp_get_wtime();
    bitflipbyte(data,(unsigned int)ceil(NUM_DATA_BYTES/32.0),k1);
    double end_time = omp_get_wtime();

    printf ("\r\nData out:\r\n");
    for (unsigned int j = 0; j < 4; j++)
    {
        for (unsigned int i = 0; i < DISPLAY_WIDTH; i++)
        {
            printf ("0x%02x,",data[i+(j*DISPLAY_WIDTH)]);
        }
        printf ("\r\n");
    }
    printf("\r\n\r\nTime to bitflip %d bytes: %f seconds\r\n\r\n",NUM_DATA_BYTES, end_time-start_time);

    // return with no errors
    return 0;
}


printf用于调试。.

这是最主要的功能:

bits 64
global bitflipbyte

bitflipbyte:    
        vmovdqa     ymm2, [rdx]
        add         rdx, 20h
        vmovdqa     ymm3, [rdx]
        add         rdx, 20h
        vmovdqa     ymm4, [rdx]
bitflipp_loop:
        vmovdqa     ymm0, [rdi] 
        vpand       ymm1, ymm2, ymm0 
        vpandn      ymm0, ymm2, ymm0 
        vpsrld      ymm0, ymm0, 4h 
        vpshufb     ymm1, ymm4, ymm1 
        vpshufb     ymm0, ymm3, ymm0         
        vpor        ymm0, ymm0, ymm1
        vmovdqa     [rdi], ymm0
        add     rdi, 20h
        dec     rsi
        jnz     bitflipp_loop
        ret


代码占用32个字节,然后掩盖了半字节。高半字节右移4。然后,我将vpshufb和ymm4 / ymm3用作查找表。我可以使用单个查找表,但是在再次对四位进行“或”运算之前,我必须先向左移动。但是我绑定到单线程和CPU,所以这是我能达到的最快速度。您可以制作一个更快的版本吗?

评论


您应为此获得更多的赞誉。我知道这对pshub应该可行,因为毕竟最好的popcount也可以做到!如果不适合您,我会在这里写的。荣誉

– Iwillnotexist Idonotexist
15年3月27日在21:24

谢谢! “ popcnt”是我的另一个最喜欢的主题;)查看我的BMI2版本:result = __ tzcnt_u64(〜_pext_u64(data [i],data [i])));

– Anders Cedronius
2015年4月1日在8:36

命名asm文件:bitflip_asm.s然后:yasm -f elf64 bitflip_asm.s命名c文件:bitflip.c然后:g ++ -fopenmp bitflip.c bitflip_asm.o -o bitflip就是这样。

– Anders Cedronius
16年7月5日在9:23



英特尔CPU在端口1上都具有popcnt,tzcnt和pext的执行单元。因此,每个pext或tzcnt都会花费您一定的吞吐量。如果您的数据在L1D缓存中很热,则在AVX2 pshufb上对Intel CPU进行阵列计数的最快方法是。 (Ryzen每时钟有4个popcnt吞吐量,因此这可能是最佳的,但是Bulldozer系列每4个时钟有1个popcnt r64,r64吞吐量... agner.org/optimize)。

– Peter Cordes
17年9月20日在10:50

我自己正在使用内部版本。但是,当我回答时,我发布了我所拥有的内容,并且从以前的文章中知道,一旦我编写汇编器,总会聪明地指出我应该在内部函数中做到这一点。当我开发程​​序时,我会先编写汇编程序,然后,当我喜欢结果时,我会转向内在函数。就是我..当我只有“测试”汇编程序版本时,我刚好发布了答案。

– Anders Cedronius
17年9月20日在14:27

#3 楼

好吧,这肯定不会像Matt J那样回答,但希望它仍然有用。

这条称为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指令的可用性,维基百科列出了1989年发布的BSWAP指令,其中包含80846。维基百科还指出,该指令仅适用于32位寄存器,这在我的机器上显然不是这种情况,它仅适用于64位寄存器。数据类型,因此可以通过传递所需的字节数来简单地泛化该方法: br />
编译器应该能够优化掉多余的参数(假设编译器内联函数),并且对于sizeof(size_t)情况,右移将被完全消除。请注意,如果传递了sizeof(char),则GCC至少不能删除BSWAP并向右移位。

评论


根据英特尔指令集参考卷2A(intel.com/content/www/us/en/processors/…),有两条BSWAP指令:BSWAP r32(在32位寄存器上工作),编码为0F C8 + rd和BSWAP r64(适用于64位寄存器),其编码为REX.W + 0F C8 + rd。

– Nubok
2014年6月19日下午16:21

您说它可以像这样使用:“ n = reverse(n,sizeof(size_t)); // reverse 64 bits”但是,除非所有常量都扩展到64bit,否则它将只给出32bits的结果。

–rajkosto
17年8月14日在3:04

从C ++ 11开始,@ rajkosto允许的整数文字类型包括unsigned long long int,该长度必须至少为64位,如此处所述

– SirGuy
17年8月14日在12:55

好?我只是说,如果要对64位值进行处理,则必须扩展文字(例如,它们为0xf0f0f0f0f0f0f0f0f0ull),否则结果的高32位将全部为0。

–rajkosto
17年8月17日在9:27

@rajkosto啊,我误解了您的第一条评论,现在我已经解决了

– SirGuy
17年8月17日在14:10

#4 楼

这是对喜欢递归的人们的另一种解决方案。

这个想法很简单。
将输入分成两半,交换两半,直到达到单比特为止。

(请注意,我使用了无符号整数,因此它可以用于sizeof(unsigned int)* 8位以下的输入。 br />要反转,并且值中的位数为


评论


这种方法在24位示例(第3个)上是否行不通?我对C和按位运算符不太熟悉,但是从您对该方法的解释中,我猜是24-> 12-> 6-> 3(3位不均匀地拆分)。由于numBits是int,当您将3除以2用作函数参数时,它将舍入为1?

–布伦南
16年5月18日在3:38



#5 楼

Anders Cedronius的答案为拥有带有AVX2支持的x86 CPU的人们提供了一个很好的解决方案。对于不支持AVX的x86平台或非x86平台,以下两种实现方式都应该可以正常工作。 -plus-logic习惯用法在各种ARM处理器上很有用。此外,它使用动态掩码生成,这对于RISC处理器可能是有益的,否则它需要多个指令来加载每个32位掩码值。用于x86平台的编译器应在编译时而不是运行时使用常量传播来计算所有掩码。

 
在D. Knuth的“计算机编程的艺术”第4A卷中,展示了一种巧妙的方式来反转位,与传统的二进制分区算法相比,这种方式有些令人惊讶地需要更少的操作。我在TAOCP中找不到这种针对32位操作数的算法,该文档在Hacker's Delight网站上显示。

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


使用Intel编译器C / C ++编译器13.1.3.198,上述两个函数都可以针对/* 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; } 寄存器很好地自动矢量化。也可以不费吹灰之力手动对其进行矢量化处理。使用XMM秒。我注意确保基准不受系统内存带宽的限制。

评论


@JoelSnyder我以“很多魔术数字”来假设您主要是指brev_knuth()? 《黑客的喜悦》中PDF的归属似乎表明这些数字直接来自于Knuth本人。我不能声称已经充分理解了Knuth对TAOCP中基本设计原理的描述,无法解释常数的派生方式,或者对于任意字长如何推导常数和移位因子。

– njuffa
2015年12月12日在18:28

#6 楼

假设您有一个位数组,该怎么做:
1.从MSB开始,将位一个一位地推入堆栈。数组(如果要节省空间),则将第一个弹出的位放入MSB中,然后从该位置继续进行不重要的位。


评论


这个让我笑了:)我很乐意看到此C#解决方案相对于上面我在优化C语言中概述的解决方案之一的基准。

–马特J
09年4月14日在6:41

大声笑...但是,嘿!最佳算法中的形容词“最佳”是一个很主观的东西:D

–弗雷德里克的傻瓜
09年4月14日在9:45

#7 楼

本机ARM指令“ rbit”可以用1个cpu周期和1个额外的cpu寄存器来完成此操作,这是不可能的。

#8 楼

对于人类来说,这不是没有工作! ...但是非常适合一台机器

这是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指令提供了艺术品级的代码,运行时间为11秒,可处理约10亿个reverse()。假设每个reverse()约为10 ns,如果假设2 GHz将使我们处于甜蜜的20个CPU周期,则需要0.5 ns的CPU周期。
一次访问一个大型数组需要一次访问RAM!
两次访问L2缓存LUT所需的时间可以设置1 reverse()。作为一个不错的基准已经存在了几年,但是一旦编译器足够聪明地优化main()以便仅打印finf最终结果而不是真正计算任何东西,它最终将开始显示它的年龄。但目前,它可以用于展示reverse()。

评论


位反转是如此普遍...我对此一无所知。我几乎每天都在使用处理位级数据的代码,而我从未想起曾经有这种特定需求。在什么情况下需要? -不是说它本身不是一个有趣的问题。

– 500-内部服务器错误
2015年12月12日在17:23

@ 500-InternalServerError我最终在语法推断中需要多次使用快速,简洁的数据结构来使用此功能。编码为位数组的普通二叉树最终以“大端”顺序推断语法。但是,为了更好地概括,如果您构建一个树(位数组),并通过位反转排列交换节点,则学习到的语法字符串应为“小端”。通过这种切换,您可以推断出可变长度的字符串,而不是固定的整数大小。这种情况也会在高效FFT中大量出现:请参见en.wikipedia.org/wiki/Bit-reversal_permutation

–user2875414
2015年12月12日20:48在

谢谢,我设法以某种方式直觉FFT可能与您的答案有关:)

– 500-内部服务器错误
2015年12月12日在21:05

为什么只有20个周期?哪种架构?在人类和世系消失之前,未来的所有超宽VLIW架构都是如此吗?只是问题,没有答案...再次下地狱

– Quonux
17年4月11日在20:15



#9 楼

当然,可疑的黑客行为的明显来源在这里:
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


这与进位一起使用,因此您也可以保存标志/>

评论


我猜您可以使用asm关键字,这会非常快。

–tom
2015年1月5日于17:22

这甚至行不通。我认为您希望rcl将CF移至var1,而不是不读取标志的shl。 (或adc dx,dx)。即使有了该修复程序,使用慢速循环指令并将var1保留在内存中,这仍然是非常可笑的!实际上,我认为这应该在AX中产生输出,但是它会在结果之上保存/恢复AX的旧值。

– Peter Cordes
18年7月13日在12:53

#11 楼

以低内存和最快的速度实现。

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


#12 楼

嗯,这基本上与第一个“ reverse()”相同,但是它是64位,只需要一个立即掩码即可从指令流中加载。 GCC创建代码时不会跳转,因此应该非常快。

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


#13 楼

我很好奇明显的原始旋转会有多快。 br优点:所需的内存很少,代码很简单。我要说的也不是很大。对于任何输入,所需的时间都是可预测的且恒定的(128个算术SHIFT运算+ 64个逻辑AND运算+ 64个逻辑OR运算)。接受的答案。如果我正确地阅读了他的答案,那么他得到的最好结果是27.28 ns次迭代0.631739,这导致平均每转1,000,000

我使用的代码段如下:

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


评论


@不确定,我不确定我是否理解您的问题。

–玛丽安·亚当
2015年4月30日20:26在

感谢您注意到错误,我修复了提供的代码示例。

–玛丽安·亚当
2015年5月1日17:39

#14 楼

您可能要使用标准模板库。它可能比上面提到的代码慢。但是,在我看来,它更清晰,更容易理解。

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


#15 楼

通用

C代码。以1字节输入数据num为例。

    unsigned char num = 0xaa;   // 1010 1010 (aa) -> 0101 0101 (55)
    int s = sizeof(num) * 8;    // get number of bits
    int i, x, y, p;
    int var = 0;                // make var data type to be equal or larger than num

    for (i = 0; i < (s / 2); i++) {
        // extract bit on the left, from MSB
        p = s - i - 1;
        x = num & (1 << p);
        x = x >> p;
        printf("x: %d\n", x);

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

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

    printf("new: 0x%x\n", new);


评论


该问题要求“最有效”,而不是“简单/直接”。

– Peter Cordes
18年7月13日在12:54

#16 楼

怎么样:

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


小巧(虽然,仅32位)。

评论


这个问题要求“最有效”;我们可以排除循环32次。 (尤其是不要移动掩膜以及必须将结果向下移动到LSB)

– Peter Cordes
18年7月13日在12:57

#17 楼

我认为这是逆转位的最简单方法之一。
请告诉我这种逻辑是否存在缺陷。
基本上,我们会检查该位置的位的值。
如果反转位置的值为1,则设置该位。

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


评论


该问题要求“最有效”,而不是“简单/直接”。

– Peter Cordes
18年7月13日在13:00

#18 楼

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


评论


有趣,但是用运行时变量进行除法很慢。 k始终是2的幂,但是编译器可能不会证明这一点并将其转换为位扫描/移位。

– Peter Cordes
18年7月13日在13:02

#19 楼

我认为我知道最简单的方法。输入MSB并反向输出LSB

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.


#20 楼

// 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


#21 楼

另一个基于循环的解决方案,当数量较少时快速退出(在C ++中为多种类型) />
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;
}


#22 楼

似乎还有许多其他帖子都在关注速度(即最佳=最快)。
那么简单呢?请考虑:

char ReverseBits(char character) {
    char reversed_character = 0;
    for (int i = 0; i < 8; i++) {
        char ith_bit = (c >> i) & 1;
        reversed_character |= (ith_bit << (sizeof(char) - 1 - i));
    }
    return reversed_character;
}


,并希望聪明的编译器能够为您优化。位),则可以使用此函数获取:

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


这会将[10000000,10101010]反转为[01010101,00000001]。

评论


您在内部循环中有3个班次。用ith_bit =(c >> i)&1保存一个。也可以通过移动reversed_char而不是移动该位来保存SUB,除非您希望它可以在x86上编译为sub / bts reg,reg来设置第n位在目标寄存器中。

– Peter Cordes
18年7月13日在13:09



#23 楼

高效意味着吞吐量或延迟。
对于整个过程,请参阅Anders Cedronius的回答,这是一个很好的选择。
对于较低的延迟,我建议使用以下代码:
uint32_t reverseBits( uint32_t x )
{
#if defined(__arm__) || defined(__aarch64__)
    __asm__( "rbit %0, %1" : "=r" ( x ) : "r" ( x ) );
    return x;
#endif
    // Flip pairwise
    x = ( ( x & 0x55555555 ) << 1 ) | ( ( x & 0xAAAAAAAA ) >> 1 );
    // Flip pairs
    x = ( ( x & 0x33333333 ) << 2 ) | ( ( x & 0xCCCCCCCC ) >> 2 );
    // Flip nibbles
    x = ( ( x & 0x0F0F0F0F ) << 4 ) | ( ( x & 0xF0F0F0F0 ) >> 4 );

    // Flip bytes. CPUs have an instruction for that, pretty fast one.
#ifdef _MSC_VER
    return _byteswap_ulong( x );
#elif defined(__INTEL_COMPILER)
    return (uint32_t)_bswap( (int)x );
#else
    // Assuming gcc or clang
    return __builtin_bswap32( x );
#endif
}

编译器输出:https://godbolt.org/z/5ehd89

#24 楼

伪代码中的位反转

源->要反转的字节b00101100
目标->反转,也需要为无符号类型,因此不能向下传播符号位

复制到临时文件中以使原始文件不受影响,还需要为无符号类型,以使符号位不会自动移位。次
测试字节复制是否<0(负数)

bytecopy = b0010110


#25 楼

我的简单解决方案

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;


评论


我是什么另外,那个魔法常数* 4是多少?是CHAR_BIT / 2吗?

– Peter Cordes
18年7月13日在13:05

#26 楼

这是32位,如果考虑8位,则需要更改大小。

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


以LSB-> MSB顺序读取输入整数“ num”,并以MSB-> LSB顺序存储在num_reverse中。

评论


您应该在代码中添加解释,以便于理解。

–Tunaki
15年8月19日在8:51