algorithme derrière la génération de la table de conversion de bits inverse (8 bits)

J’ai trouvé la table de recherche ici. La table est générée comme une table de bits inverse de 8 bits.

Je ne peux pas comprendre pourquoi cela fonctionne. S’il vous plaît expliquer la théorie derrière elle. Merci

static const unsigned char BitReverseTable256[256] = { # define R2(n) n, n + 2*64, n + 1*64, n + 3*64 # define R4(n) R2(n), R2(n + 2*16), R2(n + 1*16), R2(n + 3*16) # define R6(n) R4(n), R4(n + 2*4 ), R4(n + 1*4 ), R4(n + 3*4 ) R6(0), R6(2), R6(1), R6(3) }; 

Tout d’abord un commentaire: Ce genre de chose est normalement fait uniquement dans le IOCCC . Un tel code ne doit pas être utilisé dans les environnements de production car il n’est pas évident . La raison pour laquelle je mentionne ceci est pour supprimer la fausse impression que cela présente un avantage en termes de performances ou d’espace, le code compilé contiendra le même nombre d’octets que vous obtiendriez si vous écriviez les 256 nombres directement dans le tableau.

Ok, maintenant comment ça marche. Cela fonctionne bien sûr de manière récursive, en définissant deux bits au plus haut niveau R6, puis deux autres au suivant … Mais comment en détail? D’accord:

Le premier indice que vous obtenez est la séquence intéressante 0-> 2-> 1-> 3. Vous devriez vous demander ” pourquoi? “. C’est le bloc de construction nécessaire à la construction. Les nombres en binary 0 1 2 3 sont 00 01 10 11 et si vous inversez chacun: 00 10 01 11 ce qui est 0 2 1 3!

Voyons maintenant ce que nous voulons que le tableau fasse: Il devrait ressembler à ceci:

 00000000 10000000 01000000 11000000 00100000 10100000 01100000 11100000 00010000 10010000 01010000 11010000 00110000 10110000 01110000 11110000 ... 

parce que vous voulez qu’il mappe l’index 0 à 0, l’index 00000001 à 10000000 et ainsi de suite.

Notez que les 2 bits les plus significatifs (les plus à gauche) de chaque nombre: 00 10 01 11 pour chaque ligne!

Remarquez maintenant que les 2 bits les plus significatifs de chaque nombre augmentent de la même manière (00 10 01 11) mais pour les “colonnes”.

La raison pour laquelle j’ai choisi de classer le tableau en lignes de longueur 4 est que nous avons découvert que 2 bits sont écrits à la fois et que 2 bits peuvent créer 4 modèles.

Si vous continuez ensuite d’observer les numéros restants de la table (256 entrées au total), vous verrez que les 3ème 2 bits peuvent être trouvés avec la séquence 00 10 01 11 si vous commandez la table en colonnes de 16 et les 2 derniers bits lorsque vous commandez-le en colonnes de 64.

Maintenant, je vous ai implicitement dit d’où venaient les nombres 16 et 64 de la macro-expansion d’origine.

Tels sont les détails, et à généraliser: le niveau le plus élevé de la récursivité génère les 2 bits les moins significatifs, les deux niveaux du milieu agissent et le niveau le plus bas génère les 2 bits les plus significatifs.