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

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++...

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

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.

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

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

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().

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

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

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

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

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

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

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

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

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

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

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

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.

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

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

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

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.

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;

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.

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