Bit twiddling Neuordnungs

Question

Ich brauche eine beliebige Neuordnungs eines 7-Bit-Wert zu tun (Ja ich weiß, sollte ich eine Tabelle verwenden) und frage mich, ob es irgendwelche Bit-Hacks sind, dies zu tun.

Beispiel:

// <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

---

edit: Ich dachte an etwas entlang der Linien von dieser

Nur für Kicks und weil ich AFTK Ich bin eine Brute-Force-Suche nach Lösungen der Form versuchen:

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

Keine Lösungen gefunden.

Answer 1

Haben Sie einen Blick auf dem Compiler-Ausgang Ihres „naiven“ Code, könnte es Sie überrascht. Ich habe einmal etwas ähnliches und den Compiler (VC ++ 2005) vollständig die Werte aller ands und Verschiebungen für mich geändert, um sie effizienter zu machen, zum Beispiel ich bin sicher, es wäre Ihre „(0x001 & In) entfernen >> 3" .

Aber ja, wenn die Kabinettsumbildung eine feste Funktion ist dann eine Tabelle ist wahrscheinlich am besten.

Aktualisieren

Für ein Lachen ich an der Compiler Ausgabe von VC sah ++ 2005 ....

Zuerst habe ich versucht, einen konstanten Wert für „In“ aber der Compiler wurde kein bisschen getäuscht, es erzeugt diesen Code:

mov eax,469h

dh. es es vollständig wegoptimiert.

So ... Ich habe versucht, einen richtigen Eingang und bekam diese:

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 

Das sind vier Schaltvorgänge, fünf ANDs, vier OPs - nicht schlecht für sechs Eingänge. Wahrscheinlich besser als die meisten Menschen, die von Hand tun könnten.

Es ist wahrscheinlich auch für Out-of-Order-Ausführung optimiert, so dass es weniger Taktzyklen sein wird, als es scheint. : -)

Answer 2

Der erste Schritt scheint eine mathematische Lösung zu sein, zu verstehen, und dass optimieren.

siehe hier von Bit Hacks

Answer 3

Es gibt eine Vielzahl von Bit-twiddling hackt für allgemeine Operationen, das heißt, die Reihenfolge der Bits umgekehrt in einem 32-Bit-Wort (10 jedes der Verschiebung, AND und OR, AFAICR).

In diesem Fall mit einer scheinbar völlig willkürlichen Zuordnung von Eingang zu Ausgang, kann ich nicht sehen, jede Möglichkeit, dies zu säubern.

Verwenden Sie eine Lookup-Tabelle:)

Answer 4

Bevor Sie zu optimieren, sollten Sie sicherstellen, dass Ihre ‚naiv‘ Art und Weise tut, was Sie beabsichtigen. Wenn ich Ihren Code in eine Funktion machen und diese Schleife laufen:

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

Es erzeugt diese Ausgabe, die die Kommentare widerspricht. In der Tat, verliert es Bits.

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

Um die Shuffle Sie beschreiben zu bekommen, ich würde es so Code:

   //    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 ;