Moyen efficace pour OU bits adjacents en entier 64 bits

Question

Ce que je veux faire est de prendre une 64-bit unsigned integer composé de paires de bits et de créer à partir d'un entier de 32 bits contenant 0 si les deux bits de la paire correspondante sont 0 et 1 sinon. En d'autres termes, de convertir quelque chose qui ressemble à :

01 00 10 11

en quelque chose qui ressemble à ceci

1 0 1 1

Les deux solutions évidentes sont la force brute de la boucle ou une table de recherche pour chaque octet, puis faire huit recherches et de les combiner dans un résultat final avec OU et le décalage de bits, mais je suis sûr qu'il doit être un moyen efficace de bit-tourner cette. Je le ferai pour les entiers 64 bits en C++, mais si quelqu'un connaît un moyen efficace de le faire pour de courtes entiers je suis sûr que je peux comprendre comment à l'échelle.

Answer 1

Ici, c'est un portable C++ mise en œuvre. Il semble fonctionner au cours de mon bref essai. Le deinterleave code est basé sur cette SORTE de question.

uint64_t calc(uint64_t n)
{
    // (odd | even)
    uint64_t x = (n & 0x5555555555555555ull) | ((n & 0xAAAAAAAAAAAAAAAAull) >> 1);

    // deinterleave
    x = (x | (x >> 1)) & 0x3333333333333333ull;
    x = (x | (x >> 2)) & 0x0F0F0F0F0F0F0F0Full;
    x = (x | (x >> 4)) & 0x00FF00FF00FF00FFull;
    x = (x | (x >> 8)) & 0x0000FFFF0000FFFFull;
    x = (x | (x >> 16)) & 0x00000000FFFFFFFFull;

    return x;
}

gcc, clang, et msvc tous compiler cette baisse à environ 30 instructions.

D'après les commentaires, il y a une modification qui peut être fait.

• Modifiez la première ligne à utiliser un seul masque de fonctionnement pour sélectionner uniquement les "bizarre" de bits.

L', peut-être (?) l'amélioration du code est:

uint64_t calc(uint64_t n)
{
    // (odd | even)
    uint64_t x = (n | (n >> 1)) & 0x5555555555555555ull; // single bits

    // ... the restdeinterleave
    x = (x | (x >> 1)) & 0x3333333333333333ull; // bit pairs
    x = (x | (x >> 2)) & 0x0F0F0F0F0F0F0F0Full; // nibbles
    x = (x | (x >> 4)) & 0x00FF00FF00FF00FFull; // octets
    x = (x | (x >> 8)) & 0x0000FFFF0000FFFFull; // halfwords
    x = (x | (x >> 16)) & 0x00000000FFFFFFFFull; // words

    return x;
}

Answer 2

Solution probablement la plus rapide pour l'architecture x86 avec le jeu d'instructions BMI2 :

 #include <stdint.h>
#include <x86intrin.h>

uint32_t calc (uint64_t a)
{
   return _pext_u64(a, 0x5555555555555555ull) |
          _pext_u64(a, 0xaaaaaaaaaaaaaaaaull);
}
 

Cela compile à 5 instructions au total.

Answer 3

Si vous ne disposez pas d' pext et vous voulez toujours faire mieux que le trivial, alors cette extraction peut être exprimée comme un nombre logarithmique (si vous généralisée en termes de longueur) de bits passe:

// OR adjacent bits, destroys the odd bits but it doesn't matter
x = (x | (x >> 1)) & rep8(0x55);
// gather the even bits with delta swaps
x = bitmove(x, rep8(0x44), 1);   // make pairs
x = bitmove(x, rep8(0x30), 2);   // make nibbles
x = bitmove(x, rep4(0x0F00), 4); // make bytes
x = bitmove(x, rep2(0x00FF0000), 8); // make words
res = (uint32_t)(x | (x >> 16)); // final step is simpler

Avec:

bitmove(x, mask, step) {
    return x | ((x & mask) >> step);
}

repk est si j'ai pu écrire moins constantes. rep8(0x44) = 0x4444444444444444 etc.

Aussi, si vous n' avez pext, vous pouvez le faire avec un seul d'entre eux, ce qui est probablement plus rapide et au moins plus courte:

_pext_u64(x | (x >> 1), rep8(0x55));

Answer 4

Bien, nous allons le rendre plus hacky ensuite (peut-être buggé):

uint64_t x;

uint64_t even_bits = x & 0xAAAAAAAAAAAAAAAAull;
uint64_t odd_bits  = x & 0x5555555555555555ull;

Maintenant, ma solution originale fait:

// wrong
even_bits >> 1;
unsigned int solution = even_bits | odd_bits;

Cependant, comme JackAidley souligné, alors qu'il aligne les morceaux entre eux, elle ne supprime pas les espaces du moyen!

Heureusement, nous pouvons utiliser une très serviable _pext instruction de la BMI2 jeu d'instructions.

u64 _pext_u64(u64 a, u64 m) - Extrait de bits à partir d'un sur le bit correspondant endroits spécifiés par le masque m contiguës, les bits de poids faible de l'heure d'été; le reste des bits de poids à l'heure d'été sont mis à zéro.

solution = _pext_u64(solution, odd_bits);

Sinon, au lieu d'utiliser & et >> de séparer les morceaux, vous pouvez simplement utiliser _pext deux fois sur le numéro d'origine avec les masques (qui serait divisé en deux contigus des nombres de 32 bits), et puis tout simplement or les résultats.

Si vous n'avez pas accès à BMI2, si, je suis sûr que l'écart de suppression de nécessiterait quand même une boucle; un peu plus simple que votre idée originale, peut-être.

Answer 5

Légère amélioration par rapport à l'approche LUT (4 recherches au lieu de 8):

Calcule le bitwise ou efface tous les autres bits. Ensuite, entrelacez les bits de paires d'octets pour obtenir quatre octets. Enfin, réorganisez les bits dans les quatre octets (mappés sur le mot quad) à l'aide d'une table de correspondance de 256 entrées:

 Q= (Q | (Q << 1)) & 0xAAAAAAAAAAAAL; // OR in pairs
Q|= Q >> 9; // Intertwine 4 words into 4 bytes
B0= LUT[B0]; B1= LUT[B2]; B2= LUT[B4]; B3= LUT[B6]; // Rearrange bits in bytes