Bit twiddling réordonner

Question

J'ai besoin de faire une réorganisation arbitraire d'une valeur de 7 bits (Oui, je sais que je devrais utiliser une table) et je me demande s'il ya des hacks peu pour le faire.

Exemple:

// <b0, b1, b2, b3, b4, b5, b6> -> <b3, b2, b4, b1, b5, b0, b6> 

// the naive way 
out = 
    (0x020 & In) << 5 | 
    (0x008 & In) << 2 | 
    (0x040 & In)  | 
    (0x012 & In) >> 1 | 
    (0x004 & In) >> 2 | 
    (0x001 & In) >> 3; 

// 6 ANDs, 5 ORs, 5 shifts = 16 ops 

---

modifier: Je pensais à quelque chose le long des lignes de this

Juste pour voir et parce que je suis en train o AFTK je une force brute rechercher des solutions du formulaire:

((In * C1) >> C2) & 0x7f 

Aucune solution trouvée.

Answer 1

Jetez un oeil à la sortie du compilateur de code « naïf », il pourrait vous surprendre. J'ai déjà fait quelque chose comme ça et le compilateur (VC++ 2005) a complètement changé les valeurs de tous les ands et les changements pour moi pour les rendre plus efficaces, par exemple je suis sûr qu'il enlèverait votre "(0x001 & In) >> 3 ".

Mais oui, si le remaniement est une fonction fixe alors une table est probablement la meilleure.

Mise à jour

Pour rire, je regardais la sortie du compilateur de VC++ 2005 ....

D'abord, j'ai essayé une valeur constante pour « In », mais le compilateur n'était pas dupé un bit , il a produit ce code:

mov eax,469h 

ie. il l'a complètement optimisé.

Alors ... J'ai essayé une bonne entrée et a obtenu ceci:

00401D4F mov   eax,ecx 
00401D51 and   eax,20h 
00401D54 shl   eax,3 
00401D57 mov   edx,ecx 
00401D59 and   edx,8 
00401D5C or   eax,edx 
00401D5E mov   edx,ecx 
00401D60 sar   edx,1 
00401D62 and   edx,2 
00401D65 or   edx,ecx 
00401D67 sar   edx,1 
00401D69 shl   eax,2 
00401D6C and   edx,9 
00401D6F or   eax,edx 
00401D71 and   ecx,40h 
00401D74 or   eax,ecx 

C'est quatre quarts de travail, cinq, quatre ANDs - ORs pas mal pour six entrées. Probablement mieux que la plupart des gens pourraient faire à la main.

Il est probablement aussi optimisé pour une exécution hors de l'ordre, il y aura donc moins de cycles d'horloge qu'il n'y paraît. :-)

Answer 2

Il y a beaucoup de hacks de bits-twiddling pour les opérations courantes, c'est-à-dire pour inverser l'ordre des bits dans un mot de 32 bits (10 chacun de décalage, AND et OR, AFAICR).

Dans ce cas, avec un mappage apparemment complètement arbitraire de l'entrée à la sortie, je ne vois aucun moyen de nettoyer cela.

Utilisez une table de recherche :)

Answer 3

La première étape semble être de comprendre une solution mathématique et d'optimiser cela.

voir ici des bit hacks

Answer 4

Avant d'optimiser, vous devez vous assurer que votre chemin fait « naïf » ce que vous avez l'intention.Si je fais votre code dans une fonction et exécuter cette boucle:

for (b=0;b<7;b++) 
{ 
    i=1<<b; 
    printf("%d: %02x -> %02x\n", b, i, shuffle(i)); 
} 

Il produit cette sortie, ce qui contredit les commentaires. En fait, il perd des bits.

0: 01 -> 00 
1: 02 -> 01 
2: 04 -> 01 
3: 08 -> 20 
4: 10 -> 08 
5: 20 -> 00 
6: 40 -> 40 

Afin d'obtenir la lecture aléatoire que vous décrivez, je coder comme ceci:

// 0 1 2 3 4 5 6 
    //-> 3 2 4 1 5 0 6 
    (0x001 & In) << 3 | 
    (0x004 & In) << 2 | 
    (0x020 & In)  | 
    (0x012 & In) << 1 | 
    (0x008 & In) >> 2 | 
    (0x020 & In) >> 5 ;