Effizienter Algorithmus zur Bitumkehr (von MSB-> LSB zu LSB-> MSB) in C.

243

Was ist der effizienteste Algorithmus, um Folgendes zu erreichen:

0010 0000 => 0000 0100

Die Konvertierung erfolgt von MSB-> LSB zu LSB-> MSB. Alle Bits müssen umgekehrt werden. Das heißt, dies ist kein Endianness-Swapping.

green_t
quelle
1
Ich denke, der passende Name ist eine bitweise Operation.
Kredns
5
Ich denke, Sie meinten Umkehrung, nicht Rotation.
Juliano
2
Die meisten ARM-Prozessoren haben dafür einen eingebauten Betrieb. Der ARM Cortex-M0 funktioniert nicht, und ich fand, dass die Verwendung einer Per-Byte-Tabelle zum Austauschen von Bits der schnellste Ansatz ist.
Starblue
2
Siehe auch Sean Eron Andersons Bit Twiddling Hacks .
JWW
2
Bitte definieren Sie "am besten"
Lee Taylor

Antworten:

497

HINWEIS : Alle unten aufgeführten Algorithmen sind in C, sollten jedoch in die Sprache Ihrer Wahl portierbar sein (sehen Sie mich nur nicht an, wenn sie nicht so schnell sind :)

Optionen

Geringer Speicher (32-Bit- int, 32-Bit-Computer) (von hier ):

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

}

Von der berühmten Bit Twiddling Hacks-Seite :

Am schnellsten (Nachschlagetabelle) :

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

Sie können diese Idee auf 64-Bit- intDateien erweitern oder den Speicher gegen Geschwindigkeit austauschen (vorausgesetzt, Ihr L1-Datencache ist groß genug) und 16 Bit gleichzeitig mit einer Nachschlagetabelle mit 64 KB-Einträgen umkehren.


Andere

Einfach

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

Schneller (32-Bit-Prozessor)

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

Schneller (64-Bit-Prozessor)

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

Wenn Sie dies mit 32 Bit tun möchten int, kehren Sie einfach die Bits in jedem Byte um und kehren Sie die Reihenfolge der Bytes um. Das ist:

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

Ergebnisse

Ich habe die beiden vielversprechendsten Lösungen verglichen, die Nachschlagetabelle und das bitweise UND (die erste). Die Testmaschine ist ein Laptop mit 4 GB DDR2-800 und einem Core 2 Duo T7500 mit 2,4 GHz und 4 MB L2-Cache. YMMV. Ich habe gcc 4.3.2 unter 64-Bit-Linux verwendet. OpenMP (und die GCC-Bindungen) wurden für hochauflösende Timer verwendet.

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

Ich habe beide Ansätze bei verschiedenen Optimierungen ausprobiert, 3 Versuche auf jeder Ebene durchgeführt und jeder Versuch 100 Millionen zufällige Versuche rückgängig gemacht unsigned ints. Für die Option für die Nachschlagetabelle habe ich beide Schemata (Optionen 1 und 2) ausprobiert, die auf der Seite für bitweise Hacks angegeben sind. Die Ergebnisse sind unten gezeigt.

Bitweises UND

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

Nachschlagetabelle (Option 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  

Nachschlagetabelle (Option 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

Fazit

Verwenden Sie die Nachschlagetabelle mit Option 1 (die Byteadressierung ist nicht überraschend langsam), wenn Sie Bedenken hinsichtlich der Leistung haben. Wenn Sie das letzte Byte Speicher aus Ihrem System herausholen müssen (und wenn Sie sich für die Leistung der Bitumkehr interessieren), sind die optimierten Versionen des bitweisen UND-Ansatzes auch nicht allzu schäbig.

Vorbehalt

Ja, ich weiß, dass der Benchmark-Code ein vollständiger Hack ist. Vorschläge zur Verbesserung sind mehr als willkommen. Dinge, die ich weiß:

  • Ich habe keinen Zugang zu ICC. Dies kann schneller sein (bitte antworten Sie in einem Kommentar, wenn Sie dies testen können).
  • Eine 64K-Nachschlagetabelle kann auf einigen modernen Mikroarchitekturen mit großem L1D gut funktionieren.
  • -mtune = native hat bei -O2 / -O3 nicht funktioniert (es ldist ein verrückter Fehler bei der Neudefinition von Symbolen aufgetreten ), daher glaube ich nicht, dass der generierte Code für meine Mikroarchitektur optimiert ist.
  • Möglicherweise gibt es eine Möglichkeit, dies mit SSE etwas schneller zu tun. Ich habe keine Ahnung wie, aber mit der schnellen Replikation, dem bitweisen UND und den Anweisungen zum Swizzeln muss da etwas sein.
  • Ich kenne nur genug x86-Assembly, um gefährlich zu sein. Hier ist der Code-GCC, der auf -O3 für Option 1 generiert wurde, damit jemand, der besser informiert ist als ich, ihn überprüfen kann:

32-Bit

.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

EDIT: Ich habe es auch versucht uint64_t Typen auf meinem Computer zu verwenden, um festzustellen, ob es eine Leistungssteigerung gab. Die Leistung war etwa 10% schneller als die von 32-Bit und war nahezu identisch, unabhängig davon, ob Sie nur 64-Bit-Typen zum gleichzeitigen Umkehren von Bits auf zwei 32-Bit- intTypen verwendeten oder ob Sie tatsächlich Bits in halb so vielen 64-Bit-Typen umkehrten. Bitwerte. Der Assembler-Code wird unten gezeigt (für den ersteren Fall Umkehren von Bits für zwei 32-Bit- intTypen gleichzeitig):

.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.
quelle
2
-1 für übermäßig detaillierte und gründliche Post. j / k. +1.
Mpen
8
Es war eine interessante Übung, wenn nicht allzu erfüllend. Wenn nichts anderes, hoffe ich, dass der Prozess für jemanden konstruktiv ist, der etwas Verdienstvolleres bewerten möchte :)
Matt J
5
Mein Gott! Ich glaube, ich habe ... was sehr gut sein kann ... ein WAHRES Exemplar gefunden. Ich werde meine Dokumente konsultieren und weitere Nachforschungen anstellen müssen, aber irgendetwas sagt mir (Gott, hilf mir), dass dies bei weitem die größte, gründlichste und nützlichste Antwort ist, die Stack Overflow bisher hat. Sogar John Skeet wäre sowohl entsetzt als auch beeindruckt!
Zeboidlund
3
Beachten Sie, dass ein besonderer Fehler beim Mikrobenchmarking (neben einer Liste von vielen anderen) darin besteht, dass es dazu neigt, Lösungen auf der Basis von Nachschlagetabellen künstlich zu bevorzugen. Da der Benchmark die eine Operation in einer Schleife wiederholt, wird häufig festgestellt, dass die Verwendung einer Nachschlagetabelle, die nur in L1 passt, am schnellsten ist, da in L1 jedes Mal alles getroffen wird, da überhaupt kein Cache-Druck besteht. In einem realen Anwendungsfall wird die Operation normalerweise mit anderen Operationen verschachtelt, die einen gewissen Cache-Druck verursachen. Ein RAM-Fehler kann 10 oder 100 Mal länger dauern als gewöhnlich, wird jedoch in Benchmarks ignoriert.
BeeOnRope
2
Das Ergebnis ist, dass ich, wenn zwei Lösungen nahe beieinander liegen, häufig die Nicht-LUT-Lösung (oder die mit der kleineren LUT) auswähle, da die tatsächlichen Auswirkungen einer LUT schwerwiegend sein können. Noch besser wäre es, jede Lösung "in situ" zu bewerten - wo sie tatsächlich in der größeren Anwendung verwendet wird, mit realistischem Input. Natürlich haben wir nicht immer Zeit dafür und wir wissen nicht immer, was realistischer Input ist.
BeeOnRope
80

Dieser Thread hat meine Aufmerksamkeit erregt, da er sich mit einem einfachen Problem befasst, das selbst für eine moderne CPU viel Arbeit (CPU-Zyklen) erfordert. Und eines Tages stand ich auch mit dem gleichen ¤ #% "#" Problem da. Ich musste Millionen von Bytes umdrehen. Ich weiß jedoch, dass alle meine Zielsysteme auf modernem Intel basieren. Beginnen wir also mit der Optimierung auf das Äußerste !!!

Also habe ich Matt Js Lookup-Code als Basis verwendet. Das System, auf dem ich ein Benchmarking durchführe, ist ein i7 haswell 4700eq.

Matt Js Lookup-Bitflipping 400 000 000 Bytes: Ungefähr 0,272 Sekunden.

Ich ging dann voran und versuchte zu sehen, ob Intels ISPC-Compiler die Arithmetik in umgekehrter Reihenfolge vektorisieren konnte. C.

Ich werde Sie hier nicht mit meinen Erkenntnissen langweilen, da ich viel versucht habe, dem Compiler bei der Suche nach Dingen zu helfen. Trotzdem hatte ich eine Leistung von ungefähr 0,15 Sekunden, um 400 000 000 Bytes zu bitflippen. Es ist eine großartige Reduzierung, aber für meine Anwendung ist das immer noch viel zu langsam.

Die Leute ließen mich den schnellsten Intel-basierten Bitflipper der Welt vorstellen. Getaktet um:

Zeit zum Bitflip 400000000 Bytes: 0.050082 Sekunden !!!!!

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

Die printf's sind zum Debuggen ..

Hier ist das Arbeitstier:

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

Der Code benötigt 32 Bytes und maskiert dann die Knabbereien. Das hohe Halbbyte wird um 4 nach rechts verschoben. Dann verwende ich vpshufb und ymm4 / ymm3 als Nachschlagetabellen. Ich könnte eine einzelne Nachschlagetabelle verwenden, aber dann müsste ich nach links wechseln, bevor ich die Knabbereien wieder zusammenfügen kann.

Es gibt noch schnellere Möglichkeiten, die Bits umzudrehen. Aber ich bin an Single Thread und CPU gebunden, also war dies die schnellste, die ich erreichen konnte. Kannst du eine schnellere Version machen?

Bitte machen Sie keine Kommentare zur Verwendung der Intel C / C ++ Compiler Intrinsic Equivalent-Befehle ...

Anders Cedronius
quelle
2
Sie verdienen weit mehr positive Stimmen als diese. Ich wusste, dass dies machbar sein sollte pshub, denn schließlich wird auch der beste Popcount damit gemacht! Ich hätte es hier geschrieben, wenn nicht für dich. Ein großes Lob.
Iwillnotexist Idonotexist
3
Vielen Dank! 'popcnt' ist ein weiteres Lieblingsfach von mir;) Schauen Sie sich meine BMI2-Version an: result = __ tzcnt_u64 (~ _pext_u64 (data [i], data [i]));
Anders Cedronius
3
Benennen Sie die asm-Datei: bitflip_asm.s dann: yasm -f elf64 bitflip_asm.s Benennen Sie die c-Datei: bitflip.c dann: g ++ -fopenmp bitflip.c bitflip_asm.o -o bitflip Das ist es.
Anders Cedronius
4
Intel-CPUs haben die Ausführungseinheiten für popcnt, tzcntund pextalle an Port 1. Also kostet jeder pextoder jeder tzcntSie einen popcntDurchsatz. Wenn Ihre Daten im L1D-Cache heiß sind, können Sie ein Array auf Intel-CPUs am schnellsten mit AVX2 pshufb zählen. (Ryzen hat einen popcntDurchsatz von 4 pro Takt , das ist wahrscheinlich optimal, aber die Bulldozer-Familie hat einen Durchsatz von 4 pro Takt popcnt r64,r64... agner.org/optimize ).
Peter Cordes
4
Ich verwende selbst eine Intrinsics-Version. Als ich jedoch antwortete, schrieb ich, was ich hatte, und ich wusste aus früheren Beiträgen, dass ein kluger Aleck, sobald ich Assembler schreibe, immer darauf hinweist, dass ich es eigentlich hätte tun sollen. Wenn ich mich entwickle, schreibe ich zuerst Assembler, wenn mir das Ergebnis gefällt, wechsle ich zu Intrinsics. Das bin ich. Ich habe gerade meine Antwort gepostet, als ich nur meine Test-Assembler-Version hatte.
Anders Cedronius
16

Dies ist eine weitere Lösung für Leute, die Rekursion lieben.

Die Idee ist einfach. Teilen Sie die Eingabe durch die Hälfte und tauschen Sie die beiden Hälften aus. Fahren Sie fort, bis das einzelne Bit erreicht ist.

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

Hier ist eine rekursive Funktion, um es zu lösen. (Hinweis: Ich habe vorzeichenlose Ints verwendet, damit es für Eingaben bis zu einer Größe von (vorzeichenlosen Int) * 8 Bit verwendet werden kann.

Die rekursive Funktion akzeptiert 2 Parameter - den Wert, dessen Bits umgekehrt werden müssen, und die Anzahl der Bits im Wert.

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

Dies ist die Ausgabe:

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
quelle
Funktioniert dieser Ansatz beim 24-Bit-Beispiel (3.) nicht? Ich bin mit C- und bitweisen Operatoren nicht ganz vertraut, aber aus Ihrer Erklärung des Ansatzes schätze ich 24-> 12-> 6-> 3 (3 Bits ungleichmäßig zu teilen). Wie numBitsist int, wenn Sie 3 durch 2 für den Funktionsparameter teilen, wird es auf 1 abgerundet?
Brennan
13

Nun, dies wird sicherlich keine Antwort wie die von Matt J sein, aber hoffentlich wird es immer noch nützlich sein.

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

Dies ist genau die gleiche Idee wie bei Matts bestem Algorithmus, außer dass es diesen kleinen Befehl namens BSWAP gibt, der die Bytes (nicht die Bits) einer 64-Bit-Zahl vertauscht. So wird aus b7, b6, b5, b4, b3, b2, b1, b0 b0, b1, b2, b3, b4, b5, b6, b7. Da wir mit einer 32-Bit-Nummer arbeiten, müssen wir unsere bytegetauschte Nummer um 32 Bit nach unten verschieben. Dies lässt uns nur die Aufgabe, die 8 Bits jedes Bytes auszutauschen, was erledigt ist und voila! Wir sind fertig.

Timing: Auf meinem Computer lief Matts Algorithmus in ~ 0,52 Sekunden pro Versuch. Meins lief in ungefähr 0,42 Sekunden pro Versuch. 20% schneller ist nicht schlecht, denke ich.

Wenn Sie sich Sorgen über die Verfügbarkeit der Anweisung BSWAP Wikipedia machen listet den Befehl BSWAP als mit 80846 hinzugefügt auf, der 1989 herauskam. Es sollte beachtet werden, dass Wikipedia auch angibt, dass dieser Befehl nur mit 32-Bit-Registern funktioniert, was eindeutig nicht der Fall ist Fall auf meinem Computer funktioniert es sehr viel nur auf 64-Bit-Registern.

Diese Methode funktioniert für jeden integralen Datentyp gleich gut, sodass die Methode trivial verallgemeinert werden kann, indem die gewünschte Anzahl von Bytes übergeben wird:

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

was dann wie folgt aufgerufen werden kann:

    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

Der Compiler sollte in der Lage sein, den zusätzlichen Parameter zu optimieren (vorausgesetzt, der Compiler integriert die Funktion), und für den sizeof(size_t)Fall würde die Rechtsverschiebung vollständig entfernt. Beachten Sie, dass GCC zumindest nicht in der Lage ist, BSWAP und Rechtsverschiebung zu entfernen, wenn es bestanden wird sizeof(char).

SirGuy
quelle
2
Gemäß dem Intel Instruction Set Reference Volume 2A ( intel.com/content/www/us/en/processors/… ) gibt es zwei BSWAP-Anweisungen: BSWAP r32 (arbeitet mit 32-Bit-Registern), das als 0F C8 + rd codiert ist und BSWAP r64 (arbeitet an 64-Bit-Registern), das als REX.W + 0F C8 + rd codiert ist.
Nubok
Sie sagen, es kann wie folgt verwendet werden: "n = reverse (n, sizeof (size_t)); // 64 Bit umkehren", dies ergibt jedoch nur 32 Bit Ergebnis, es sei denn, alle Konstanten werden auf 64 Bit erweitert, dann funktioniert es.
Rajkosto
@rajkosto ab C ++ 11 die zulässigen Arten von Integer-Literalen enthalten, unsigned long long intdie mindestens 64 Bit sein müssen, wie hier und hier
SirGuy
Okay? Ich sage nur, wenn Sie möchten, dass dies mit 64-Bit-Werten funktioniert, müssen Sie Ihre Literale erweitern (so sind sie beispielsweise 0xf0f0f0f0f0f0f0f0ull), andernfalls sind die hohen 32 Bit des Ergebnisses alle Nullen.
Rajkosto
@rajkosto Ah, ich hatte Ihren ersten Kommentar falsch verstanden, ich habe das jetzt
behoben
13

Die Antwort von Anders Cedronius bietet eine großartige Lösung für Benutzer mit einer x86-CPU mit AVX2-Unterstützung. Für x86-Plattformen ohne AVX-Unterstützung oder Nicht-x86-Plattformen sollte eine der folgenden Implementierungen gut funktionieren.

Der erste Code ist eine Variante der klassischen binären Partitionierungsmethode, die so codiert ist, dass die Verwendung des auf verschiedenen ARM-Prozessoren nützlichen Shift-Plus-Logik-Idioms maximiert wird. Darüber hinaus wird die On-the-Fly-Maskengenerierung verwendet, was für RISC-Prozessoren von Vorteil sein kann, die ansonsten mehrere Anweisungen zum Laden jedes 32-Bit-Maskenwerts benötigen. Compiler für x86-Plattformen sollten eine konstante Weitergabe verwenden, um alle Masken zur Kompilierungszeit und nicht zur Laufzeit zu berechnen.

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

In Band 4A von "The Art of Computer Programming" zeigt D. Knuth clevere Möglichkeiten zum Umkehren von Bits, die überraschenderweise weniger Operationen erfordern als die klassischen binären Partitionierungsalgorithmen. Ein solcher Algorithmus für 32-Bit-Operanden, den ich in TAOCP nicht finden kann, wird in diesem Dokument auf der Hacker's Delight-Website gezeigt.

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

Mit dem Intel Compiler C / C ++ - Compiler 13.1.3.198 werden beide oben genannten Funktionen automatisch vektorisiert XMM Registerregister . Sie können auch ohne großen Aufwand manuell vektorisiert werden.

Auf meinem IvyBridge Xeon E3 1270v2 wurden unter Verwendung des automatisch vektorisierten Codes 100 Millionen uint32_tWörter in 0,070 Sekunden mit brev_classic()und 0,068 Sekunden mit bitumgekehrt brev_knuth(). Ich habe darauf geachtet, dass mein Benchmark nicht durch die Bandbreite des Systemspeichers begrenzt ist.

Njuffa
quelle
2
@JoelSnyder Ich nehme an, mit "vielen magischen Zahlen", auf die Sie sich hauptsächlich beziehen brev_knuth()? Die Zuschreibung im PDF von Hacker's Delight scheint darauf hinzudeuten, dass diese Zahlen direkt von Knuth selbst stammen. Ich kann nicht behaupten, Knuths Beschreibung der zugrunde liegenden Entwurfsprinzipien in TAOCP ausreichend verstanden zu haben, um zu erklären, wie die Konstanten abgeleitet wurden oder wie man die abgeleiteten Konstanten und Verschiebungsfaktoren für beliebige Wortgrößen vorgehen würde.
Njuffa
8

Angenommen, Sie haben ein Array von Bits, wie wäre es damit: 1. Schieben Sie die Bits ausgehend von MSB nacheinander in einen Stapel. 2. Pop-Bits von diesem Stapel in ein anderes Array (oder dasselbe Array, wenn Sie Platz sparen möchten), platzieren Sie das erste Popped-Bit in MSB und fahren Sie von dort aus mit weniger signifikanten Bits fort.

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();
}
Friedrich der Narr
quelle
3
Dieser brachte mich zum Lächeln :) Ich würde gerne einen Benchmark dieser C # -Lösung gegen einen der oben in optimiertem C skizzierten sehen.
Matt J
LOL ... Aber hey! Das Adjektiv 'best' im 'besten Algorithmus' ist eine ziemlich subjektive Sache: D
Frederick The Fool
7

Der native ARM-Befehl "rbit" kann dies mit 1 CPU-Zyklus und 1 zusätzlichen CPU-Register tun, was unschlagbar ist.

Metalogic
quelle
6

Für einen Menschen ist das kein Job! ... aber perfekt für eine Maschine

Dies ist 2015, 6 Jahre nachdem diese Frage zum ersten Mal gestellt wurde. Compiler sind seitdem unsere Meister geworden, und unsere Aufgabe als Mensch ist es nur, ihnen zu helfen. Was ist der beste Weg, um der Maschine unsere Absichten zu geben?

Bit-Umkehrung ist so häufig, dass Sie sich fragen müssen, warum die ständig wachsende ISA des x86 keine Anweisung enthält, dies auf einmal zu tun.

Der Grund: Wenn Sie dem Compiler Ihre wahre, präzise Absicht geben, sollte die Bitumkehr nur ~ 20 CPU-Zyklen dauern . Lassen Sie mich Ihnen zeigen, wie Sie reverse () herstellen und verwenden:

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

Das Kompilieren dieses Beispielprogramms mit der Clang-Version> = 3.6, -O3, -march = native (getestet mit Haswell) liefert Code in Grafikqualität unter Verwendung der neuen AVX2-Anweisungen mit einer Laufzeit von 11 Sekunden , die ~ 1 Milliarde reverse () s verarbeitet. Das sind ~ 10 ns pro Umkehrung (), wobei ein CPU-Zyklus von 0,5 ns bei 2 GHz die süßen 20 CPU-Zyklen erreicht.

  • Sie können 10 reverse () s in die Zeit einpassen, die benötigt wird, um einmal auf RAM für ein einzelnes großes Array zuzugreifen!
  • Sie können 1 reverse () in die Zeit einpassen, die für den zweimaligen Zugriff auf eine L2-Cache-LUT erforderlich ist.

Vorsichtsmaßnahme: Dieser Beispielcode sollte einige Jahre lang als anständiger Maßstab dienen, aber er wird irgendwann sein Alter zeigen, sobald die Compiler klug genug sind, main () zu optimieren, um nur das Endergebnis auszudrucken, anstatt wirklich etwas zu berechnen. Aber im Moment funktioniert es, um reverse () zu präsentieren.

Samuel Liew
quelle
Bit-reversal is so common...Das weiß ich nicht. Ich arbeite mit Code, der praktisch jeden Tag mit Daten auf Bitebene umgeht, und ich kann mich nicht erinnern, jemals dieses spezielle Bedürfnis gehabt zu haben. In welchen Szenarien brauchen Sie es? - Nicht, dass es kein interessantes Problem wäre, es selbst zu lösen.
500 - Interner
@ 500-InternalServerError Am Ende brauche ich diese Funktion oft in Grammatik-Inferenzen mit schnellen, prägnanten Datenstrukturen. Ein normaler Binärbaum, der als Bitarray codiert ist, leitet die Grammatik in der Reihenfolge "Big Endian" ab. Zur besseren Verallgemeinerung, wenn Sie einen Baum (Bitarray) mit Knoten erstellen, die durch die Bitumkehrpermutation vertauscht wurden, sind die Zeichenfolgen der gelernten Grammatik in "Little Endian". Durch diese Umschaltung können Sie auf Zeichenfolgen mit variabler Länge anstatt auf feste Ganzzahlgrößen schließen. Diese Situation taucht auch bei effizienter FFT häufig auf: siehe en.wikipedia.org/wiki/Bit-reversal_permutation
1
Danke, ich habe es irgendwie geschafft zu verstehen, dass FFT an Ihrer Antwort beteiligt sein könnte :)
500 - Interner
warum nur 20 Zyklen? Welche Architektur? Gilt das für alle superweiten VLIW-Architekturen der Zukunft, bis die Menschheit und unsere Nachkommen aussterben? Nur Fragen, keine Antworten ... wieder zur Hölle
abstimmen
5

Ich weiß, es ist nicht C, sondern asm:

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

Dies funktioniert mit dem Übertragsbit, sodass Sie auch Flags speichern können

Coco
quelle
1
Ich denke, Sie könnten das Schlüsselwort asm verwenden , was ziemlich schnell wäre.
Tom
Das funktioniert nicht einmal. Ich denke, Sie möchten rclCF verschieben var1, anstatt nur shlFlags zu lesen. (Oder adc dx,dx). Selbst mit diesem Fix ist dies lächerlich langsam, wenn man die langsame loopAnweisung verwendet und var1im Gedächtnis bleibt ! Eigentlich denke ich, dass dies die Ausgabe in AX erzeugen soll, aber es speichert / stellt den alten Wert von AX über dem Ergebnis wieder her.
Peter Cordes
4

Implementierung mit wenig Speicher und am schnellsten.

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
quelle
4

Nun, dies ist im Grunde dasselbe wie das erste "reverse ()", aber es ist 64 Bit und benötigt nur eine sofortige Maske, um aus dem Befehlsstrom geladen zu werden. GCC erstellt Code ohne Sprünge, daher sollte dies ziemlich schnell gehen.

#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;
}
Wildplasser
quelle
4

Ich war gespannt, wie schnell die offensichtliche Rohrotation sein würde. Auf meinem Computer (i7 @ 2600) lag der Durchschnitt für 1.500.150.000 Iterationen 27.28 ns(über einen zufälligen Satz von 131.071 64-Bit-Ganzzahlen).

Vorteile: Der Speicherbedarf ist gering und der Code einfach. Ich würde sagen, es ist auch nicht so groß. Die erforderliche Zeit ist für jede Eingabe vorhersehbar und konstant (128 arithmetische SHIFT-Operationen + 64 logische UND-Operationen + 64 logische ODER-Operationen).

Ich habe mit der besten Zeit verglichen, die @Matt J erhalten hat - der die akzeptierte Antwort hat. Wenn ich seine Antwort richtig lese, ist das Beste, was er hat, 0.631739Sekunden für 1,000,000Iterationen, was zu einem Durchschnitt von 631 nspro Umdrehung führt.

Das Code-Snippet, das ich verwendet habe, ist das folgende:

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
quelle
@ Greybeard Ich bin nicht sicher, ob ich Ihre Frage verstehe.
Marian Adam
Vielen Dank, dass Sie den Fehler bemerkt haben. Ich habe das bereitgestellte Codebeispiel behoben.
Adam
3

Möglicherweise möchten Sie die Standardvorlagenbibliothek verwenden. Es ist möglicherweise langsamer als der oben genannte Code. Es scheint mir jedoch klarer und leichter zu verstehen.

 #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;  
 }
Cem
quelle
2

Generisch

C-Code. Verwenden Sie als Beispiel die 1-Byte-Eingabedaten 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);
Vjangus
quelle
Die Frage lautete "am effizientesten", nicht "einfach / unkompliziert".
Peter Cordes
1

Wie wäre es mit folgendem:

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

Klein und einfach (allerdings nur 32 Bit).

BlueAutumn
quelle
Die Frage nach "am effizientesten" gestellt; Wir können eine 32-malige Schleife ausschließen. (Und vor allem nicht die Maske verschieben sowie das Ergebnis auf das LSB verschieben müssen)
Peter Cordes
1

Ich dachte, dies ist einer der einfachsten Wege, um das Bit umzukehren. Bitte lassen Sie mich wissen, wenn diese Logik fehlerhaft ist. Grundsätzlich überprüfen wir in dieser Logik den Wert des Bits in Position. Setzen Sie das Bit, wenn der Wert in umgekehrter Position 1 ist.

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;    
}    
Arun Nagendran
quelle
Die Frage lautete "am effizientesten", nicht "einfach / unkompliziert".
Peter Cordes
0
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;
}
user3615967
quelle
Interessant, aber die Division durch eine Laufzeitvariable ist langsam. kist immer eine Potenz von 2, aber Compiler werden das wahrscheinlich nicht beweisen und es in Bit-Scan / Shift umwandeln.
Peter Cordes
0

Ich denke, die einfachste Methode, die ich kenne, folgt. MSBist Eingabe und LSBist 'umgekehrte' Ausgabe:

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.
user7726695
quelle
0
// 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
MikhailJacques
quelle
0

Eine weitere schleifenbasierte Lösung, die schnell beendet wird, wenn die Anzahl niedrig ist (in C ++ für mehrere Typen).

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

oder in C für ein vorzeichenloses 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;
}
Daniel Santos
quelle
0

Es scheint, dass viele andere Beiträge über die Geschwindigkeit besorgt sind (dh am besten = am schnellsten). Was ist mit Einfachheit? Erwägen:

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

und hoffe, dass der clevere Compiler für Sie optimiert.

Wenn Sie eine längere Liste von Bits (die sizeof(char) * nBits enthalten ) umkehren möchten , können Sie diese Funktion verwenden, um Folgendes zu erhalten:

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

Dies würde [10000000, 10101010] in [01010101, 00000001] umkehren.

mercury0114
quelle
Sie haben 3 Schichten in der inneren Schleife. Speichern Sie eine mit ith_bit = (c >> i) & 1. Auch speichert SUB durch Verschieben reversed_charstatt das Stück verschoben wird , es sei denn , Sie hoffen , es auf x86 kompilieren wird sub something/ bts reg,regdas n - te Bit im Zielregister zu setzen.
Peter Cordes
-1

Bitumkehr im Pseudocode

Quelle -> umzukehrendes Byte b00101100 Ziel -> umgekehrt, muss ebenfalls vom Typ ohne Vorzeichen sein, damit das Vorzeichenbit nicht nach unten übertragen wird

Kopieren in Temp, damit das Original nicht betroffen ist. Es muss auch vom Typ ohne Vorzeichen sein, damit das Vorzeichenbit nicht automatisch verschoben wird

bytecopy = b0010110

LOOP8: // Diesen 8-maligen Test durchführen, wenn die Bytekopie <0 ist (negativ)

    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.
Peter Sikora
quelle
-1

Meine einfache Lösung

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;
Ivan Hionidi
quelle
1
Was ist i? Was ist diese magische Konstante * 4? Ist es CHAR_BIT / 2?
Peter Cordes
-1

Dies ist für 32 Bit, wir müssen die Größe ändern, wenn wir 8 Bit berücksichtigen.

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

Lesen der Eingabe-Ganzzahl "num" in der Reihenfolge LSB-> MSB und Speichern in num_reverse in der Reihenfolge MSB-> LSB.

karthik kalakodimi
quelle
1
Sie sollten dem Code eine Erklärung hinzufügen, damit er leichter verstanden wird.
Tunaki
-3
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;
}
Shihao Xu
quelle
3
Im Allgemeinen sind Antworten viel hilfreicher, wenn sie eine Erklärung enthalten, was der Code tun soll und warum dies das Problem löst.
IKavanagh