Algorithme le plus efficace pour L'inversion de bits (DE MSB->LSB à LSB->MSB) en C [fermé]

Quel est le meilleur algorithme pour obtenir ce qui suit:

0010 0000 => 0000 0100

la conversion est de MSB->LSB à LSB->MSB. Tous les bits doivent être inversés, c'est-à-dire qu'il s'agit de et non de .

222
demandé sur BeeOnRope 2009-04-14 06:48:46

26 réponses

NOTE : 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 :)

Options

peu de Mémoire (32 bits int , machine 32 bits)(à partir de 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 Peu Tourner les Hacks page :

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 s, ou échanger la mémoire pour la vitesse (en supposant que votre Cache de données L1 est assez grand), et inverser 16 bits à la fois avec une table de recherche 64K-entrée.


autres

Simple

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 voulez faire cela sur un 32 bits int , juste inverser les bits de chaque octet, et d'inverser l'ordre des octets. C'est-à-dire:

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-et (la première). La machine de test est un ordinateur portable w / 4GB de DDR2-800 et un noyau 2 Duo T7500 @ 2,4 GHz, 4MB L2 Cache; YMMV. J'ai utilisé gcc 4.3.2 sous Linux 64 bits. OpenMP (et les fixations GCC) ont été utilisés pour les minuteries à haute résolution.

inverse.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 à différents optimisations, a couru 3 essais à chaque niveau, et chaque essai inversé 100 millions aléatoire 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 des hacks bitwise. Les résultats sont présentés ci-dessous.

Bitwise et

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 bytes est sans surprise lent) si vous êtes préoccupé par la performance. Si vous avez besoin de presser chaque octet de mémoire hors de votre système (et vous pourriez, Si vous vous souciez de la performance de l'inversion de bits), les versions optimisées du bitwise-and approach ne sont pas trop mal non plus.

mise en garde

Oui, je sais que le code de référence est un piratage complet. Suggestions pour l'améliorer sont plus que bienvenus. Ce que je sais:

  • Je n'ai pas accès à la CPI. Cela peut être plus rapide (veuillez répondre dans un commentaire si vous pouvez la tester).
  • UN 64 ko table de recherche peut s'effectuer sur certains modernes microarchitectures avec de grandes L1D.
  • - mtune=natif n'a pas fonctionné pour-O2/ - O3 ( ld a explosé avec une erreur de redéfinition de symbole folle), donc je ne crois pas que le code généré est accordé pour ma microarchitecture.
  • il peut y avoir un moyen de le faire un peu plus rapidement avec le SSE. Je n'ai aucune idée de comment, mais avec une réplication rapide, un package bitwise et, et des instructions swizzling, il doit y avoir quelque chose là.
  • Je ne connais qu'assez de x86 assembly pour être dangereux; voici le code GCC généré on-O3 pour l'option 1, donc quelqu'un de plus informé que

32-peu

.L3:
movl    (%r12,%rsi), %ecx
movzbl  %cl, %eax
movzbl  BitReverseTable256(%rax), %edx
movl    %ecx, %eax
shrl    , %eax
mov     %eax, %eax
movzbl  BitReverseTable256(%rax), %eax
sall    , %edx
orl     %eax, %edx
movzbl  %ch, %eax
shrl    , %ecx
movzbl  BitReverseTable256(%rax), %eax
movzbl  %cl, %ecx
sall    , %eax
orl     %eax, %edx
movzbl  BitReverseTable256(%rcx), %eax
sall    , %eax
orl     %eax, %edx
movl    %edx, (%r13,%rsi)
addq    , %rsi
cmpq    0000000, %rsi
jne     .L3

EDIT: j'ai aussi essayé d'utiliser les types uint64_t sur ma machine pour voir s'il y avait une augmentation de performance. La Performance était d'environ 10% plus rapide que 32 bits, et était presque identique que vous utilisiez des types 64 bits pour inverser des bits sur deux types 32 bits int à la fois, ou que vous inversiez des bits en deux fois moins de 64 bits valeur. Le code de l'assemblage est indiqué ci-dessous (dans le premier cas, en inversant les bits pour deux types de 32 bits int à la fois):

.L3:
movq    (%r12,%rsi), %rdx
movq    %rdx, %rax
shrq    , %rax
andl    5, %eax
movzbl  BitReverseTable256(%rax), %ecx
movzbq  %dl,%rax
movzbl  BitReverseTable256(%rax), %eax
salq    , %rax
orq     %rax, %rcx
movq    %rdx, %rax
shrq    , %rax
movzbl  BitReverseTable256(%rax), %eax
salq    , %rax
orq     %rax, %rcx
movzbl  %dh, %eax
shrq    , %rdx
movzbl  BitReverseTable256(%rax), %eax
salq    , %rax
orq     %rax, %rcx
movzbq  %dl,%rax
shrq    , %rdx
movzbl  BitReverseTable256(%rax), %eax
salq    , %rax
orq     %rax, %rcx
movzbq  %dl,%rax
shrq    , %rdx
movzbl  BitReverseTable256(%rax), %eax
salq    , %rax
orq     %rax, %rcx
movzbq  %dl,%rax
shrq    , %rdx
movzbl  BitReverseTable256(%rax), %eax
andl    5, %edx
salq    , %rax
orq     %rax, %rcx
movzbl  BitReverseTable256(%rdx), %eax
salq    , %rax
orq     %rax, %rcx
movq    %rcx, (%r13,%rsi)
addq    , %rsi
cmpq    0000000, %rsi
jne     .L3
477
répondu Matt J 2018-10-01 13:00:41

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, j'ai aussi se tenait là, avec les mêmes ¤#%"#" problème. J'ai dû retourner des millions d'octets. Cependant, je sais que tous mes systèmes cibles sont basés sur Intel moderne alors commençons à optimiser à l'extrême!!!

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

Recherche de Matt j bitflipping 400 000 000 octets: environ 0.272 secondes.

je suis alors allé de l'avant et essayé de voir si le compilateur ISPC D'Intel pourrait vectoriser l'arithmétique dans l'inverse.C.

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

donc les gens m'ont laissé présenter le bitflipper Intel le plus rapide au monde. Pointé à:

le 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 travail:

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 grignotines. La haute grignoter obtient décalé à droite par 4. Puis j'utilise vpshufb et ymm4 / ymm3 comme des tables de recherche. Je pourrais utiliser une seule table de recherche mais alors je devrais changer à gauche avant de ORing les grignotines ensemble à nouveau.

il y a des moyens encore plus rapides de retourner les bits. Mais je suis lié à fil simple et CPU donc c'était le plus rapide que j'ai pu atteindre. Pouvez-vous faire une version plus rapide?

s'il vous plaît ne faire aucun commentaire sur L'utilisation des commandes équivalentes intrinsèques du compilateur Intel C/C++...

65
répondu Anders Cedronius 2018-10-01 15:24:46

c'est une autre solution pour les gens qui aiment la récursion.

l'idée est simple. Divisez les entrées par la moitié et changez les deux moitiés, continuez jusqu'à ce qu'elles atteignent le bit simple.

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 la résoudre. (Notez que j'ai utilisé des ints non signés, de sorte qu'il peut fonctionner pour des entrées jusqu'à Size of(non signé int)*8 bits.

la fonction récursive prend 2 paramètres - la valeur dont les bits ont besoin pour être inversé 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);
}

C'est 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
13
répondu Dennis Mathews 2018-10-01 14:12:47

la réponse d'Anders Cedronius fournit une excellente solution pour les personnes qui ont un CPU x86 avec support AVX2. Pour les plates-formes x86 sans support AVX ou les plates-formes non-x86, l'une ou l'autre des implémentations suivantes devrait fonctionner correctement.

le premier code est une variante de la méthode classique de partitionnement binaire, codé pour maximiser l'utilisation de l'idiome shift-plus-logic utile sur divers processeurs ARM. En outre, il utilise à la volée masque génération ce qui pourrait être bénéfique pour les processeurs RISC qui nécessitent des instructions multiples pour charger chaque valeur de masque 32 bits. Les compilateurs de plates-formes x86 devraient utiliser la 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 de manière astucieuse de l'inversion de bits qui est quelque peu surprenant, nécessitent moins d'opérations que le classique binaire algorithmes de partitionnement. L'un de ces l'algorithme pour les opérandes 32 bits, que je ne trouve pas dans TAOCP, est montré dans ce document sur le site 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 Intel c / c++ 13.1.3.198, les deux fonctions ci-dessus auto-vectorize ciblent bien les registres XMM . Ils pourraient aussi être vectorisé manuellement, sans beaucoup d'efforts.

sur mon IvyBridge Xeon E3 1270v2, en utilisant le code auto-vectorisé, 100 millions Les mots uin32_t ont été inversés en bits en 0,070 seconde en utilisant brev_classic() et 0,068 seconde en utilisant brev_knuth() . J'ai veillé à ce que mon benchmark ne soit pas limité par la bande passante mémoire du système.

11
répondu njuffa 2017-05-23 12:03:07

Eh bien, ce ne sera certainement pas une réponse comme celle de Matt J, mais j'espère que ce sera encore 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 échange 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. Puisque nous travaillons avec un nombre de 32 bits, nous devons changer notre octets échangés nombre de 32 bits. Cela nous laisse juste avec la tâche d'échanger les 8 bits de chaque octet qui est fait et voila! nous avons terminé.

: sur ma machine, L'algorithme de Matt court en ~0.52 secondes par essai. Le mien a duré environ 0,42 seconde par procès. 20% plus rapide n'est pas mauvais je pense.

si vous êtes inquiet de la disponibilité de l'instruction BSWAP Wikipedia liste l'instruction BSWAP comme étant ajouté avec 80846 qui est sorti en 1989. Il convient de noter que Wikipedia déclare également que cette instruction ne fonctionne que sur des registres 32 bits, ce qui n'est clairement pas le cas sur ma machine, cela fonctionne très bien uniquement sur des registres 64 bits.

cette méthode fonctionnera également bien pour n'importe quel type de données intégral de sorte que la méthode peut être généralisée trivialement en passant le nombre d'octets désirés:

    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 alors ê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 la le paramètre supplémentaire est supprimé (en supposant que le compilateur allonge la fonction) et pour le cas sizeof(size_t) , le décalage de droite serait complètement supprimé. Notez que GCC au moins N'est pas capable d'enlever le BSWAP et le décalage à droite si passé sizeof(char) .

11
répondu SirGuy 2017-08-17 13:42:17

présumant que vous avez une rangée de bits, Que diriez-vous de ceci: 1. À partir de MSB, insérez des bits dans une pile un par un. 2. Pop bits de cette pile dans un autre tableau (ou le même tableau si vous voulez économiser de l'espace), placer le premier bit popped dans MSB et passer à 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();
}
8
répondu Frederick The Fool 2009-04-14 03:26:43

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

nous sommes en 2015, 6 ans après la première question. Les compilateurs sont depuis devenus nos maîtres, et notre travail en tant qu'humains n'est que de les aider. Quelle est la meilleure façon de donner nos intentions à la machine?

bit-reversement est si commun que vous devez vous demander pourquoi L'ISA toujours en croissance de x86 ne comprend pas l'instruction de 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 ~20 cycles CPU . Laissez-moi vous montrer comment faire marche arrière() 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;
}

compiler ce programme d'échantillon avec la version de Clang > = 3.6, -O3, - march=native (testé avec Haswell), donne le code de qualité d'oeuvre en utilisant les nouvelles instructions AVX2, avec un temps d'exécution de 11 secondes traitement de l' ~1 milliard inverse (). C'est ~10 ns par reverse(), avec .5 ns cycle CPU en supposant 2 GHz nous met à la sweet 20 cycles CPU.

  • vous pouvez ajuster 10 reverse()S dans le temps qu'il faut pour accéder à la RAM une fois pour un seul grand tableau!
  • vous pouvez insérer 1 reverse() dans le temps qu'il faut pour accéder à un cache L2 LUT deux fois.

avertissement: exemple de code devrait tenir comme une référence décente pendant quelques années, mais il commencera éventuellement à montrer son âge une fois que les compilateurs sont assez intelligents pour optimiser main() juste printf le résultat final au lieu de vraiment calculer quoi que ce soit. Mais pour l'instant, cela fonctionne dans showcasing reverse().

6
répondu user13972 2015-12-21 23:47:14

bien sûr, la source évidente des piratages est ici: http://graphics.stanford.edu seander bithacks.html#BitReverseObvious

5
répondu Anders Hansson 2009-04-14 07:49:09

instruction de bras natif "rbit" peut le faire avec 1 cycle cpu et 1 registre cpu supplémentaire, impossible à battre.

5
répondu metalogic 2016-04-05 22:11:35

je sais que ce n'est pas C, mais l'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 carry bit, donc vous pouvez enregistrer des drapeaux aussi

5
répondu Coco 2017-03-14 09:09:54

implémentation avec mémoire basse et la 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;
    }
4
répondu Aung 2009-10-30 08:38:11

j'étais curieux de savoir à 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 qu'elle n'est pas si grande non plus. Le temps requis est prévisible et constant pour toute entrée (128 opérations arithmétiques décalées + 64 logiques et opérations + 64 logiques ou opérations).

j'ai comparé avec le meilleur temps obtenu par @Matt J-qui a la réponse acceptée. Si je lis sa réponse correctement, le mieux qu'il a obtenu était 0.631739 secondes pour 1,000,000 itérations, ce qui conduit à une moyenne de 631 ns par rotation.

l'extrait de code que j'ai utilisé est celui 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);
}
4
répondu marian adam 2015-05-01 17:36:38

Eh bien, c'est fondamentalement le même que le premier "reverse()" mais c'est 64 bits et n'a besoin que d'un masque immédiat pour être chargé à partir du flux d'instruction. 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;
}
3
répondu wildplasser 2011-11-09 12:25:42

Vous pouvez utiliser la bibliothèque de modèles standard. Il pourrait être plus lent que le code mentionné ci-dessus. Cependant, il me semble plus claire 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;  
 }
3
répondu Cem 2012-05-31 17:13:01

Générique

C code. En utilisant le nombre de données d'entrée de 1 octet comme exemple.

    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);
2
répondu vjangus 2009-04-14 08:56:08

Que Diriez-vous de ce qui suit:

    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 (bien que, 32 bits seulement).

2
répondu BlueAutumn 2012-09-24 18:58:01

j'ai pensé que c'était l'une des façons les plus simples d'inverser le morceau. faites-moi savoir s'il y a une faille dans cette logique. fondamentalement dans cette logique, nous vérifions la valeur du bit en position. réglez le débit si la valeur est 1 sur la 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;    
}    
1
répondu Arun Nagendran 2015-12-18 16:02:47
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;
}
0
répondu user3615967 2014-05-08 11:46:09

je pense que la méthode la plus simple que je connaisse suit. MSB est entrée et LSB est sortie "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.
0
répondu user7726695 2014-06-09 17:59:32
// 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
0
répondu MikhailJacques 2014-09-17 04:51:58

une autre solution basée sur la boucle qui disparaît 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 int "151930920 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;
}
0
répondu Daniel Santos 2015-09-05 21:26:32

il semble que beaucoup d'autres messages sont préoccupés par la vitesse (I. e best = le plus rapide). Ce sujet de la simplicité? Prendre en considération:

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érer que clever compilateur optimisera pour vous.

Si vous voulez inverser une liste plus longue de bits (contenant sizeof(char) * n bits), 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].

0
répondu mercury0114 2018-07-16 10:11:49

inversion de bits en pseudo-code

source -> byte être inversée b00101100 destination - > inversé, doit également être de type non signé afin bit de signe n'est pas propogated vers le bas

copie en temp pour 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é dans automaticaly

bytecopy = b0010110

LOOP8: //le faire 8 fois test si bytecopy 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.
-1
répondu Peter Sikora 2013-06-05 10:25:26

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;
-1
répondu Ivan Hionidi 2016-08-17 13:15:24

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

Lire l'entier d'Entrée " num " dans L'ordre LSB->MSB et stocker dans num_reverse dans L'ordre MSB->LSB.

-1
répondu karthik kalakodimi 2018-02-14 16:31:42
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;
}
-3
répondu Shihao Xu 2015-10-02 04:17:36