Comment entrelacer 2 booléens à l’aide d’opérateurs au niveau des bits?

Supposons que j’ai deux valeurs de 4 bits, ABCD et abcd . Comment l’entrelacer pour qu’il devienne AaBbCcDd , en utilisant des opérateurs au niveau du bit? Exemple en pseudo-C:

 nibble a = 0b1001; nibble b = 0b1100; char c = foo(a,b); print_bits(c); // output: 0b11010010 

Remarque: 4 bits est juste pour illustration, je veux faire cela avec deux ints 32 bits.

    C’est ce qu’on appelle l’opération de mélange parfait , et cela est discuté en détail dans la Bible de Bit Bashing, Le délice du pirate par Henry Warren, section 7-2 “Mélanger les bits”.

    En supposant que x soit un entier de 32 bits avec a dans son ordre le plus élevé, 16 bits et b dans son ordre le plus bas, 16 bits:

      unsigned int x = (a << 16) | b; /* put a and b in place */ 

    le code simple et semblable à C suivant réalise le shuffle parfait:

     x = (x & 0x0000FF00) << 8 | (x >> 8) & 0x0000FF00 | x & 0xFF0000FF; x = (x & 0x00F000F0) << 4 | (x >> 4) & 0x00F000F0 | x & 0xF00FF00F; x = (x & 0x0C0C0C0C) << 2 | (x >> 2) & 0x0C0C0C0C | x & 0xC3C3C3C3; x = (x & 0x22222222) << 1 | (x >> 1) & 0x22222222 | x & 0x99999999; 

    Il donne également une forme alternative qui est plus rapide sur certains processeurs, et (je pense) un peu plus claire et extensible:

     unsigned int t; /* an intermediate, temporary variable */ t = (x ^ (x >> 8)) & 0x0000FF00; x = x ^ t ^ (t << 8); t = (x ^ (x >> 4)) & 0x00F000F0; x = x ^ t ^ (t << 4); t = (x ^ (x >> 2)) & 0x0C0C0C0C; x = x ^ t ^ (t << 2); t = (x ^ (x >> 1)) & 0x22222222; x = x ^ t ^ (t << 1); 

    Je vois que vous avez modifié votre question pour demander un résultat 64 bits de deux entrées 32 bits. Il faudrait que je réfléchisse à la manière d'étendre la technique de Warren. Je pense que ce ne serait pas trop difficile, mais je devrais y réfléchir un peu. Si quelqu'un d'autre voulait commencer ici et donner une version 64 bits, je serais ravi de le faire.

    Édité pour 64 bits

    J'ai étendu la deuxième solution à 64 bits de manière simple. J'ai d'abord doublé la longueur de chacune des constantes. Ensuite, j'ai ajouté une ligne au début pour permuter les doubles octets adjacents et les mélanger. Dans les 4 lignes suivantes, qui sont à peu près les mêmes que dans la version 32 bits, la première ligne permute les octets et les entremixes adjacents, la deuxième ligne se transforme en octets , la troisième ligne en double-bits et la dernière ligne en simple morceaux.

     unsigned long long int t; /* an intermediate, temporary variable */ t = (x ^ (x >> 16)) & 0x00000000FFFF0000ull; x = x ^ t ^ (t << 16); t = (x ^ (x >> 8)) & 0x0000FF000000FF00ull; x = x ^ t ^ (t << 8); t = (x ^ (x >> 4)) & 0x00F000F000F000F0ull; x = x ^ t ^ (t << 4); t = (x ^ (x >> 2)) & 0x0C0C0C0C0C0C0C0Cull; x = x ^ t ^ (t << 2); t = (x ^ (x >> 1)) & 0x2222222222222222ull; x = x ^ t ^ (t << 1); 

    De la page “Bit Twiddling Hacks” de Stanford: https://graphics.stanford.edu/~seander/bithacks.html#InterleaveTableObvious

      uint32_t x = /*...*/, y = /*...*/; uint64_t z = 0; for (int i = 0; i < sizeof(x) * CHAR_BIT; i++) // unroll for more speed... { z |= (x & 1U << i) << i | (y & 1U << i) << (i + 1); } 

    Regardez la page, ils proposent des algorithmes différents et plus rapides pour atteindre le même objective.

    Ainsi:

     #include  typedef unsigned int half; typedef unsigned long long full; full mix_bits(half a,half b) { full result = 0; for (int i=0; i>i)&1)<<(2*i+1))|(((b>>i)&1)<<(2*i+0)); return result; } 

    Voici une solution basée sur des boucles qui, espérons-le, est plus lisible que certaines des solutions déjà existantes.

     #include  #include  #include  uint64_t interleave(uint32_t a, uint32_t b) { uint64_t result = 0; int i; for (i = 0; i < 31; i++) { result |= (a >> (31 - i)) & 1; result <<= 1; result |= (b >> (31 - i)) & 1; result <<= 1; } // Skip the last left shift. result |= (a >> (31 - i)) & 1; result <<= 1; result |= (b >> (31 - i)) & 1; return result; } void printBits(uint64_t a) { int i; for (i = 0; i < 64; i++) printf("%lu", (a >> (63 - i)) & 1); puts(""); } int main(){ uint32_t a = 0x9; uint32_t b = 0x6; uint64_t c = interleave(a,b); printBits(a); printBits(b); printBits(c); } 

    J’ai utilisé les 2 astuces / opérations utilisées dans ce post. Comment définir, effacer et basculer un seul bit? de setting a bit at particular index et de checking the bit at particular index .

    Le code suivant est implémenté à l’aide de ces 2 opérations uniquement.

     int a = 0b1001; int b = 0b1100; long int c=0; int index; //To specify index of c int bit,i; //Set bits in c from right to left. for(i=32;i>=0;i--) { index=2*i+1; //We have to add the bit in c at this index //Check a bit=a&(1< 

    Sortie: 210 qui est 0b11010010