Entrelacement efficace des bits

Je dois faire uint64_t sur 2 uint32_t entrelacement des bits: si A=a0a1a2...a31 et B=b0b1...b31 , j’ai besoin de C = a0b0a1b1...a31b31 . Y a-t-il un moyen de le faire efficacement? Jusqu’ici, je n’ai qu’une approche naïve avec une boucle for de 32 itérations, où chaque itération fait C|=((A&(1<<i))<<i)|((B&(1<<i))<<(i+1)) .

J’imagine qu’il devrait exister une astuce mathématique, telle que la multiplication de A et B par un nombre spécial, ce qui entraîne un entrelacement de leurs bits avec des zéros dans le nombre résultant de 64 bits, de sorte qu’il ne rest que le or les produits. Mais je ne peux pas trouver un tel multiplicateur.

Une autre possibilité consiste à utiliser une instruction insortingnsèque ou d’assemblage du compilateur, mais je ne le sais pas.

Le lien de NathanOliver offre l’implémentation 16 bits -> 32 bits:

 static const unsigned int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF}; static const unsigned int S[] = {1, 2, 4, 8}; unsigned int x; // Interleave lower 16 bits of x and y, so the bits of x unsigned int y; // are in the even positions and bits from y in the odd; unsigned int z; // z gets the resulting 32-bit Morton Number. // x and y must initially be less than 65536. x = (x | (x << S[3])) & B[3]; x = (x | (x << S[2])) & B[2]; x = (x | (x << S[1])) & B[1]; x = (x | (x << S[0])) & B[0]; y = [the same thing on y] z = x | (y << 1);

Qui fonctionne par:

laissez les 8 bits de x où ils sont. Déplacez les 8 bits les plus hauts de 8;
divisez en deux et faites la même chose, en laissant cette fois les paires basses de 4 bits où elles se trouvent et en déplaçant les autres de 4;
et encore et encore.

C'est à dire que cela se passe comme:

 abcdefghijklmnop -> 00000000abcdefgh 00000000ijklmnop -> 0000abcd0000efgh 0000ijkl0000mnop -> 00ab00cd00ef00gh 00ij00kl00mn00op -> 0a0b0c0d0e0f0g0h 0i0j0k0l0m0n0o0p

Et puis combine les deux entrées ensemble.

Selon mon commentaire précédent, pour étendre cela à 64 bits, ajoutez simplement un décalage initial de 16 et un masque de 0x0000ffff0000ffff , soit parce que vous pouvez suivre intuitivement le modèle ou comme une étape de division et de conquête, transformant le problème 32 bits en deux problèmes 16 bits non se chevauchant puis en utilisant la solution 16 bits.

Une courte liste de calculs précalculée serait-elle considérée comme une “astuce mathématique”?

Précalculez un tableau de 256 uint16_t s:

 static const uint16_t lookup[256]={0x0000, 0x0001, 0x0005 ..., 0x5555};

Nous pouvons entrelacer deux valeurs de huit bits et obtenir facilement une valeur de 16 bits:

 uint16_t interleave(uint8_t a, uint8_t b) { return (lookup[a] << 1) | lookup[b]; }

Comment étendre ceci pour entrelacer deux valeurs de 32 bits en une valeur de 64 bits devrait être évident: appelez-le quatre fois, pour chacun des quatre octets constituant un uint32_t , puis << an | les résultats ensemble. Cacheter le compilateur pour aligner le tout, et le résultat final devrait être assez rapide et peu coûteux.

Puisque la mémoire RAM est bon marché de nos jours, vous pouvez également envisager une table précalculée de 65536 uint32_t s.