Algorithme efficace pour l'inversion de bits (de MSB-> LSB à LSB-> MSB) en C

243

Quel est l'algorithme le plus efficace pour atteindre les objectifs suivants:

0010 0000 => 0000 0100

La conversion est de MSB-> LSB en LSB-> MSB. Tous les bits doivent être inversés; c'est-à-dire qu'il ne s'agit pas d' échanger l'endianité.

green_t
la source
1
Je pense que le nom approprié est une opération au niveau du bit.
Kredns
5
Je pense que vous vouliez dire inversion, pas rotation.
Juliano
2
La plupart des processeurs ARM ont un fonctionnement intégré pour cela. L'ARM Cortex-M0 ne fonctionne pas, et j'ai trouvé que l'utilisation d'une table par octet pour permuter les bits était l'approche la plus rapide.
starblue
2
Voir aussi Bit Twiddling Hacks de Sean Eron Anderson .
2015
2
Veuillez définir "le meilleur"
Lee Taylor

Réponses:

497

REMARQUE : Tous les algorithmes ci-dessous sont en C, mais devraient être portables dans la langue de votre choix (ne me regardez pas quand ils ne sont pas aussi rapides :)

Les options

Mémoire faible ( intmachine 32 bits , 32 bits) (d' ici ):

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

}

De la célèbre page Bit Twiddling Hacks :

Le plus rapide (table de recherche) :

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

Vous pouvez étendre cette idée à 64 bits int, ou échanger la mémoire pour la vitesse (en supposant que votre cache de données L1 est suffisamment grand), et inverser 16 bits à la fois avec une table de recherche à 64 Ko.


Autres

Facile

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

Plus rapide (processeur 32 bits)

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

Plus rapide (processeur 64 bits)

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

Si vous souhaitez le faire sur un 32 bits int, inversez simplement les bits de chaque octet et inversez l'ordre des octets. C'est:

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

Résultats

J'ai comparé les deux solutions les plus prometteuses, la table de recherche et Bitwise-AND (la première). La machine de test est un ordinateur portable avec 4 Go de DDR2-800 et un Core 2 Duo T7500 @ 2,4 GHz, 4 Mo de cache L2; YMMV. J'ai utilisé gcc 4.3.2 sur Linux 64 bits. OpenMP (et les liaisons GCC) ont été utilisés pour les temporisateurs haute résolution.

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

J'ai essayé les deux approches avec plusieurs optimisations différentes, j'ai effectué 3 essais à chaque niveau et chaque essai a inversé 100 millions au hasard unsigned ints. Pour l'option de table de recherche, j'ai essayé les deux schémas (options 1 et 2) donnés sur la page de piratage au niveau du bit. Les résultats sont présentés ci-dessous.

ET au niveau du bit

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

Table de recherche (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  

Table de recherche (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

Conclusion

Utilisez la table de recherche, avec l'option 1 (l'adressage des octets est sans surprise lent) si vous êtes préoccupé par les performances. Si vous devez extraire chaque dernier octet de mémoire de votre système (et vous pourriez, si vous vous souciez des performances de l'inversion de bits), les versions optimisées de l'approche bit à bit ET ne sont pas trop minables non plus.

Caveat

Oui, je sais que le code de référence est un hack complet. Les suggestions sur la façon de l'améliorer sont plus que bienvenues. Ce que je sais:

  • Je n'ai pas accès à ICC. Cela peut être plus rapide (veuillez répondre dans un commentaire si vous pouvez le tester).
  • Une table de recherche de 64 Ko peut bien fonctionner sur certaines microarchitectures modernes avec un grand L1D.
  • -mtune = native ne fonctionnait pas pour -O2 / -O3 (a ldexplosé avec une erreur de redéfinition de symbole fou), donc je ne crois pas que le code généré est réglé pour ma microarchitecture.
  • Il peut y avoir un moyen de le faire un peu plus rapidement avec SSE. Je ne sais pas comment, mais avec une réplication rapide, un ET binaire et des instructions rapides, il doit y avoir quelque chose.
  • Je ne connais que suffisamment d'assemblage x86 pour être dangereux; voici le code GCC généré sur -O3 pour l'option 1, donc quelqu'un de plus compétent que moi peut le vérifier:

32 bits

.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: J'ai également essayé d'utiliser des uint64_ttypes sur ma machine pour voir s'il y avait une amélioration des performances. Les performances étaient environ 10% plus rapides que 32 bits et étaient presque identiques, que vous utilisiez simplement des types 64 bits pour inverser des bits sur deux inttypes 32 bits à la fois, ou que vous inversiez réellement des bits sur deux fois moins 64- valeurs binaires. Le code assembleur est illustré ci-dessous (pour le premier cas, inverser les bits pour deux inttypes 32 bits à la fois):

.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
la source
2
-1 pour un article trop détaillé et complet. j / k. +1.
mpen
8
Ce fut un exercice intéressant, sinon tout à fait satisfaisant. Si rien d'autre, j'espère que le processus est constructif pour quelqu'un d'autre qui voudra peut-être comparer quelque chose de plus méritoire :)
Matt J
5
Mon Dieu! Je pense que j'ai trouvé ... ce qui pourrait très bien être ... un VRAI spécimen. Je devrai consulter mes documents et faire d'autres recherches, mais quelque chose me dit (Dieu, aidez-moi), que c'est de loin la réponse la plus grande, la plus complète et la plus utile que Stack Overflow ait encore. Même John Skeet serait à la fois consterné et impressionné!
zeboidlund
3
Gardez à l'esprit qu'une faille particulière de la micro-analyse comparative (parmi une liste de nombreuses autres) est qu'elle tend à favoriser artificiellement les solutions basées sur les tables de recherche. Étant donné que le test de référence répète une opération dans une boucle, il est souvent constaté que l'utilisation d'une table de recherche qui tient juste dans L1 est la plus rapide, car tout frappera dans L1 à chaque fois car il n'y a aucune pression de cache. Dans un cas d'utilisation réel, l'opération sera généralement entrelacée avec d'autres opérations qui provoquent une certaine pression de cache. Un manquement à la RAM pourrait prendre 10 ou 100 fois plus longtemps que d'habitude, mais cela est ignoré dans les benchmarks.
BeeOnRope
2
Le résultat est que si deux solutions sont proches, je choisis souvent la solution non-LUT (ou celle avec la plus petite LUT) car l'impact réel d'une LUT peut être grave. Encore mieux serait de comparer chaque solution "in situ" - où elle est réellement utilisée dans une application plus large, avec une entrée réaliste. Bien sûr, nous n'avons pas toujours le temps pour cela, et nous ne savons pas toujours ce qu'est un apport réaliste.
BeeOnRope
80

Ce fil a attiré mon attention car il traite d'un problème simple qui nécessite beaucoup de travail (cycles CPU) même pour un CPU moderne. Et un jour, je suis resté là avec le même problème ¤ #% "#". J'ai dû retourner des millions d'octets. Cependant, je sais que tous mes systèmes cibles sont basés sur des processeurs Intel modernes, alors commençons l'optimisation à l'extrême !!!

J'ai donc utilisé le code de recherche de Matt J comme base. le système sur lequel je compare est un i7 haswell 4700eq.

La recherche de Matt J bitflipping 400 000 000 octets: environ 0,272 secondes.

Je suis ensuite allé de l'avant et j'ai essayé de voir si le compilateur ISPC d'Intel pouvait vectoriser l'arithmétique dans le sens inverse.c.

Je ne vais pas vous ennuyer avec mes découvertes ici car j'ai beaucoup essayé pour aider le compilateur à trouver des trucs, de toute façon j'ai fini avec des performances d'environ 0,15 seconde pour bitflip 400 000 000 octets. C'est une grande réduction mais pour mon application c'est encore beaucoup trop lent ..

Donc, les gens me laissent présenter le bitflipper basé sur Intel le plus rapide au monde. Pointé à:

Temps de bitflip 400000000 octets: 0,050082 secondes !!!!!

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

Les printf sont pour le débogage ..

Voici le cheval de bataille:

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

Le code prend 32 octets puis masque les grignotages. Le quartet élevé est décalé à droite de 4. Ensuite, j'utilise vpshufb et ymm4 / ymm3 comme tables de recherche. Je pourrais utiliser une seule table de recherche, mais je devrais ensuite déplacer à gauche avant de réorganiser les grignotages.

Il existe des moyens encore plus rapides de retourner les bits. Mais je suis lié au thread unique et au processeur, donc c'était le plus rapide que j'ai pu atteindre. Pouvez-vous faire une version plus rapide?

Veuillez ne faire aucun commentaire sur l'utilisation des commandes équivalentes intrinsèques du compilateur Intel C / C ++ ...

Anders Cedronius
la source
2
Vous méritez bien plus de votes positifs que cela. Je savais que cela devrait être faisable avec pshub, car après tout, le meilleur popcount est également fait avec! Je l'aurais écrit ici sans toi. Gloire.
Iwillnotexist Idonotexist
3
Merci! 'popcnt' est un autre de mes sujets préférés;) Découvrez ma version BMI2: result = __ tzcnt_u64 (~ _pext_u64 (data [i], data [i]));
Anders Cedronius
3
Nommez le fichier asm: bitflip_asm.s puis: yasm -f elf64 bitflip_asm.s Nommez le fichier c: bitflip.c puis: g ++ -fopenmp bitflip.c bitflip_asm.o -o bitflip C'est tout.
Anders Cedronius
4
Les processeurs Intel ont les unités d'exécution pour popcnt, tzcntet pexttout sur le port 1. Ainsi, chaque pextou tzcntvous coûte un popcntdébit. Si vos données sont à chaud dans le cache L1D, le moyen le plus rapide de faire un tableau sur les processeurs Intel est avec pshufb AVX2. (Ryzen a un popcntdébit de 4 par horloge, ce qui est probablement optimal, mais la famille Bulldozer a un popcnt r64,r64débit par 4 horloges ... agner.org/optimize ).
Peter Cordes
4
J'utilise moi-même une version intrinsèque. Cependant, quand j'ai répondu, j'ai posté ce que j'avais et je savais dans les articles précédents que dès que j'écris un assembleur, un smart aleck souligne toujours que j'aurais dû le faire en intrinsèque. Quand je développe, j'écris d'abord l'assembleur puis, quand j'aime le résultat, je passe à l'intrinsèque. C'est moi. Je viens de poster ma réponse alors que je n'avais que ma version d'assembleur «test».
Anders Cedronius
16

Ceci est une autre solution pour les gens qui aiment la récursivité.

L'idée est simple. Divisez l'entrée par moitié et échangez les deux moitiés, continuez jusqu'à ce qu'elle atteigne un seul bit.

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

Voici une fonction récursive pour le résoudre. (Notez que j'ai utilisé des entiers non signés, donc cela peut fonctionner pour des entrées jusqu'à sizeof (unsigned int) * 8 bits.

La fonction récursive prend 2 paramètres - La valeur dont les bits doivent être inversés et le nombre de bits dans la valeur.

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

Voici la sortie:

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
la source
Cette approche ne fonctionne-t-elle pas sur l'exemple 24 bits (3e)? Je ne connais pas très bien les opérateurs C et au niveau du bit, mais d'après votre explication de l'approche, je suppose que 24-> 12-> 6-> 3 (3 bits inégaux à diviser). Comme numBitspour int, lorsque vous divisez 3 par 2 pour la fonction param, elle sera arrondie à 1?
Brennan
13

Eh bien, ce ne sera certainement pas une réponse comme celle de Matt J, mais j'espère qu'elle sera toujours utile.

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

C'est exactement la même idée que le meilleur algorithme de Matt, sauf qu'il y a cette petite instruction appelée BSWAP qui permute les octets (pas les bits) d'un nombre 64 bits. Donc b7, b6, b5, b4, b3, b2, b1, b0 devient b0, b1, b2, b3, b4, b5, b6, b7. Étant donné que nous travaillons avec un nombre 32 bits, nous devons réduire notre nombre à octets inversés de 32 bits. Cela nous laisse juste la tâche de permuter les 8 bits de chaque octet, ce qui est fait et le tour est joué! avaient fini.

Timing: sur ma machine, l'algorithme de Matt a fonctionné en ~ 0,52 seconde par essai. Le mien a fonctionné en environ 0,42 seconde par essai. 20% plus vite ce n'est pas mal je pense.

Si vous vous inquiétez de la disponibilité de l'instruction BSWAP Wikipedia répertorie l'instruction BSWAP comme étant ajoutée avec 80846 qui est sortie en 1989. Il convient de noter que Wikipedia indique également que cette instruction ne fonctionne que sur des registres 32 bits, ce qui n'est clairement pas le cas sur ma machine, il fonctionne très bien uniquement sur les registres 64 bits.

Cette méthode fonctionnera également bien pour tout type de données intégral, de sorte que la méthode peut être généralisée de manière triviale en passant le nombre d'octets souhaité:

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

qui peut ensuite être appelé comme:

    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

Le compilateur devrait être en mesure d'optimiser le paramètre supplémentaire (en supposant que le compilateur intègre la fonction) et pour le sizeof(size_t)cas, le décalage vers la droite serait complètement supprimé. Notez que GCC au moins n'est pas en mesure de supprimer le BSWAP et le décalage à droite s'il est réussi sizeof(char).

SirGuy
la source
2
Selon l'Intel Instruction Set Reference Volume 2A ( intel.com/content/www/us/en/processors/… ), il existe deux instructions BSWAP: BSWAP r32 (fonctionnant sur des registres 32 bits), qui est codé comme 0F C8 + rd et BSWAP r64 (fonctionnant sur des registres 64 bits), qui est codé comme REX.W + 0F C8 + rd.
Nubok
Vous dites qu'il peut être utilisé comme ceci: "n = reverse (n, sizeof (size_t)); // reverse 64 bits" mais cela ne donnera que 32 bits de résultat à moins que toutes les constantes soient étendues à 64 bits, alors cela fonctionne.
rajkosto
@rajkosto à partir de C ++ 11 comprend les types autorisés de littéraux entiers unsigned long long intqui doivent être d'au moins 64 bits, comme ici et ici
SirGuy
D'accord? Je dis juste que si vous voulez que cela fonctionne sur des valeurs 64 bits, vous devez étendre vos littéraux (ils sont donc 0xf0f0f0f0f0f0f0f0ull, par exemple), sinon les 32 bits élevés du résultat seront tous des 0.
rajkosto
@rajkosto Ah, j'avais mal compris votre premier commentaire, j'ai corrigé ça maintenant
SirGuy
13

La réponse d'Anders Cedronius fournit une excellente solution pour les personnes disposant d'un processeur x86 avec prise en charge AVX2. Pour les plates-formes x86 sans prise en charge AVX ou les plates-formes non x86, l'une des implémentations suivantes devrait fonctionner correctement.

Le premier code est une variante de la méthode de partitionnement binaire classique, codée pour maximiser l'utilisation de l'idiome shift-plus-logic utile sur divers processeurs ARM. En outre, il utilise la génération de masques à la volée qui pourrait être bénéfique pour les processeurs RISC qui, autrement, nécessitent plusieurs instructions pour charger chaque valeur de masque 32 bits. Les compilateurs pour les plates-formes x86 doivent utiliser une propagation constante pour calculer tous les masques au moment de la compilation plutôt qu'au moment de l'exécution.

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

Dans le volume 4A de "The Art of Computer Programming", D. Knuth montre des façons astucieuses d'inverser des bits qui, de façon surprenante, nécessitent moins d'opérations que les algorithmes de partitionnement binaire classiques. Un tel algorithme pour les opérandes 32 bits, que je ne trouve pas dans TAOCP, est présenté dans ce document sur le site Web de 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;
}

En utilisant le compilateur C / C ++ du compilateur Intel 13.1.3.198, les deux fonctions ci-dessus s'auto-vectorisent bien XMM registres de . Ils peuvent également être vectorisés manuellement sans beaucoup d'efforts.

Sur mon IvyBridge Xeon E3 1270v2, en utilisant le code auto-vectorisé, 100 millions de uint32_tmots ont été inversés en 0,070 secondes en utilisant brev_classic()et 0,068 secondes en utilisant brev_knuth(). J'ai pris soin de m'assurer que mon benchmark n'était pas limité par la bande passante mémoire système.

njuffa
la source
2
@JoelSnyder Je suppose par "beaucoup de nombres magiques" que vous faites principalement référence brev_knuth()? L'attribution dans le PDF de Hacker's Delight semble indiquer que ces chiffres proviennent directement de Knuth lui-même. Je ne peux pas prétendre avoir suffisamment compris la description de Knuth des principes de conception sous-jacents dans TAOCP pour expliquer comment les constantes ont été dérivées, ou comment on procéderait pour dériver les constantes et les facteurs de décalage pour des tailles de mots arbitraires.
njuffa
8

En supposant que vous avez un tableau de bits, que diriez-vous de cela: 1. À partir de MSB, poussez les bits dans une pile un par un. 2. Insérez les bits de cette pile dans un autre tableau (ou le même tableau si vous souhaitez économiser de l'espace), en plaçant le premier bit extrait dans MSB et en passant à des bits moins significatifs à partir de là.

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();
}
Frédéric le fou
la source
3
Celui-ci m'a fait sourire :) J'adorerais voir une référence de cette solution C # contre l'une de celles que j'ai décrites ci-dessus dans un C. optimisé
Matt J
LOL ... Mais bon! l'adjectif «meilleur» dans le «meilleur algorithme» est une chose assez subjective: D
Frederick The Fool
7

L'instruction native ARM "rbit" peut le faire avec 1 cycle de processeur et 1 registre de processeur supplémentaire, impossible à battre.

metalogic
la source
6

Ce n'est pas un travail pour un humain! ... mais parfait pour une machine

Nous sommes en 2015, 6 ans après le début de la question. Les compilateurs sont depuis devenus nos maîtres, et notre travail en tant qu'humains n'est que de les aider. Alors, quelle est la meilleure façon de donner nos intentions à la machine?

L'inversion de bits est si courante que vous devez vous demander pourquoi l'ISA en constante augmentation du x86 n'inclut pas d'instructions pour le faire d'un seul coup.

La raison: si vous donnez votre véritable intention concise au compilateur, l'inversion de bits ne devrait prendre que ~ 20 cycles CPU . Permettez-moi de vous montrer comment créer reverse () et l'utiliser:

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

La compilation de cet exemple de programme avec la version Clang> = 3.6, -O3, -march = native (testé avec Haswell), donne un code de qualité graphique à l'aide des nouvelles instructions AVX2, avec un temps d'exécution de 11 secondes traitant ~ 1 milliard de reverse () s. C'est ~ 10 ns par reverse (), avec un cycle de processeur de 0,5 ns en supposant que 2 GHz nous place aux 20 cycles de processeur doux.

  • Vous pouvez installer 10 inverses dans le temps nécessaire pour accéder à la RAM une seule fois pour une seule grande baie!
  • Vous pouvez insérer 1 reverse () dans le temps nécessaire pour accéder à une LUT de cache L2 deux fois.

Avertissement: cet exemple de code devrait constituer une référence décente pendant quelques années, mais il commencera finalement à montrer son âge une fois que les compilateurs seront suffisamment intelligents pour optimiser main () afin d'imprimer simplement le résultat final au lieu de vraiment calculer quoi que ce soit. Mais pour l'instant, cela fonctionne en présentant reverse ().

Samuel Liew
la source
Bit-reversal is so common...Je n'en sais rien. Je travaille avec du code qui traite des données au niveau du bit pratiquement tous les jours, et je ne me souviens pas avoir jamais eu ce besoin spécifique. Dans quels scénarios en avez-vous besoin? - Non pas que ce ne soit pas un problème intéressant à résoudre à part entière.
500 - Erreur du serveur interne du
@ 500-InternalServerError Je finis par avoir besoin de cette fonction plusieurs fois dans l'inférence grammaticale avec des structures de données rapides et succinctes. Un arbre binaire normal encodé en bitarray finit par inférer la grammaire dans un ordre "big endian". Mais pour une meilleure généralisation si vous construisez un arbre (bitarray) avec des nœuds échangés par la permutation d'inversion de bits, les chaînes de la grammaire apprise sont en "petit endian". Cette commutation vous permet d'inférer des chaînes de longueur variable plutôt que des tailles entières fixes. Cette situation apparaît également beaucoup dans la FFT efficace: voir en.wikipedia.org/wiki/Bit-reversal_permutation
1
Merci, j'ai réussi à comprendre que la FFT pourrait être impliquée dans votre réponse :)
500 - Erreur du serveur interne
pourquoi seulement 20 cycles? Quelle architecture? Est-ce vrai pour toutes les architectures VLIW super larges du futur jusqu'à ce que l'humanité et nos descentes s'éteignent? Juste des questions, pas de réponses ... downvote to hell again
Quonux
5

Je sais que ce n'est pas C mais asm:

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

Cela fonctionne avec le bit de transport, vous pouvez donc également enregistrer des indicateurs

coco
la source
1
Je suppose que vous pourriez utiliser le mot-clé asm , ce qui serait assez rapide.
Tom
Ça ne marche même pas. Je pense que vous voulez rcldéplacer CF dans var1, au lieu de simplement shlne pas lire les drapeaux. (Ou adc dx,dx). Même avec ce correctif, c'est ridiculement lent, en utilisant l' loopinstruction lente et en gardant var1en mémoire! En fait, je pense que cela est censé produire la sortie dans AX, mais il enregistre / restaure l'ancienne valeur d'AX par-dessus le résultat.
Peter Cordes
4

Implémentation avec peu de mémoire et plus rapide.

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
la source
4

Eh bien, c'est fondamentalement le même que le premier "reverse ()" mais il est de 64 bits et n'a besoin que d'un masque immédiat pour être chargé à partir du flux d'instructions. GCC crée du code sans sauts, donc cela devrait être assez rapide.

#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;
}
sauvage
la source
4

J'étais curieux de voir à quelle vitesse serait la rotation brute évidente. Sur ma machine (i7 @ 2600), la moyenne pour 1 500 150 000 itérations était 27.28 ns(sur un ensemble aléatoire de 131 071 entiers 64 bits).

Avantages: la quantité de mémoire nécessaire est faible et le code est simple. Je dirais que ce n'est pas si grand non plus. Le temps requis est prévisible et constant pour toute entrée (128 opérations de décalage arithmétique + 64 opérations logiques ET + 64 opérations logiques OU).

J'ai comparé au meilleur temps obtenu par @Matt J - qui a la réponse acceptée. Si j'ai bien lu sa réponse, le meilleur qu'il a obtenu était de 0.631739quelques secondes pour les 1,000,000itérations, ce qui conduit à une moyenne 631 nspar rotation.

L'extrait de code que j'ai utilisé est celui-ci ci-dessous:

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
la source
@greybeard Je ne suis pas sûr de comprendre votre question.
marian adam
merci d'avoir remarqué le bug, j'ai corrigé l'exemple de code fourni.
marian adam
3

Vous souhaiterez peut-être utiliser la bibliothèque de modèles standard. Il peut être plus lent que le code mentionné ci-dessus. Cependant, il me semble plus clair et plus facile à comprendre.

 #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
la source
2

Générique

Code C. En utilisant l'exemple de données d'entrée 1 octet.

    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
la source
La question demandait «la plus efficace» et non «simple / directe».
Peter Cordes
1

Qu'en est-il des éléments suivants:

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

Petit et facile (cependant, 32 bits uniquement).

BlueAutumn
la source
La question demandait «le plus efficace»; nous pouvons exclure une boucle 32 fois. (Et surtout ne pas décaler le masque ainsi que devoir décaler le résultat vers le LSB)
Peter Cordes
1

Je pensais que c'était l'un des moyens les plus simples d'inverser le bit. veuillez me faire savoir s'il y a un défaut dans cette logique. Fondamentalement, dans cette logique, nous vérifions la valeur du bit en position. mettre le bit si la valeur est 1 en position inversée.

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
la source
La question demandait «la plus efficace» et non «simple / directe».
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
la source
Intéressant, mais la division par une variable d'exécution est lente. kest toujours une puissance de 2, mais les compilateurs ne le prouveront probablement pas et ne le transformeront pas en bit-scan / shift.
Peter Cordes
0

Je pense que la méthode la plus simple que je connaisse suit. MSBest une entrée et une LSBsortie «inversée»:

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
la source
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
la source
0

Une autre solution basée sur une boucle qui se ferme rapidement lorsque le nombre est faible (en C ++ pour plusieurs types)

template<class T>
T reverse_bits(T in) {
    T bit = static_cast<T>(1) << (sizeof(T) * 8 - 1);
    T out;

    for (out = 0; bit && in; bit >>= 1, in >>= 1) {
        if (in & 1) {
            out |= bit;
        }
    }
    return out;
}

ou en C pour un entier non signé

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
la source
0

Il semble que de nombreux autres articles se préoccupent de la vitesse (c'est-à-dire le meilleur = le plus rapide). Et la simplicité? Considérer:

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

et espérons que ce compilateur intelligent sera optimisé pour vous.

Si vous souhaitez inverser une liste de bits plus longue (contenant des sizeof(char) * nbits), vous pouvez utiliser cette fonction pour obtenir:

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

Cela inverserait [10000000, 10101010] en [01010101, 00000001].

mercury0114
la source
Vous avez 3 changements dans la boucle intérieure. Enregistrez-en un avec ith_bit = (c >> i) & 1. Enregistrez également un SUB en décalant reversed_charau lieu de décaler le bit, sauf si vous espérez qu'il se compilera sur x86 pour sub something/ bts reg,regpour définir le nième bit dans le registre de destination.
Peter Cordes
-1

Inversion de bits dans un pseudo-code

source -> octet à inverser b00101100 destination -> inversé, doit également être de type non signé pour que le bit de signe ne soit pas propagé vers le bas

la copie dans temp afin que l'original ne soit pas affecté, doit également être de type non signé pour que le bit de signe ne soit pas décalé automatiquement

bytecopy = b0010110

LOOP8: // effectuez ce test 8 fois si la copie parallèle est <0 (négatif)

    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
la source
-1

Ma solution simple

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
la source
1
Quoi i? Aussi, quelle est cette constante magique * 4? C'est ça CHAR_BIT / 2?
Peter Cordes
-1

C'est pour 32 bits, nous devons changer la taille si nous considérons 8 bits.

    void bitReverse(int num)
    {
        int num_reverse = 0;
        int size = (sizeof(int)*8) -1;
        int i=0,j=0;
        for(i=0,j=size;i<=size,j>=0;i++,j--)
        {
            if((num >> i)&1)
            {
                num_reverse = (num_reverse | (1<<j));
            }
        }
        printf("\n rev num = %d\n",num_reverse);
    }

Lecture de l'entier d'entrée "num" dans l'ordre LSB-> MSB et stockage dans num_reverse dans l'ordre MSB-> LSB.

karthik kalakodimi
la source
1
Vous devez ajouter une explication au code afin qu'il soit mieux compris.
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
la source
3
Généralement, les réponses sont beaucoup plus utiles si elles incluent une explication de ce que le code est censé faire et pourquoi cela résout le problème.
IKavanagh