Erläuterung zum Drehen einer Bitmap um 90 °

Question

Ich habe kürzlich that SO question gefunden.

Die angenommene Antwort und die Antwort von Rhubbarb funktioniert gut, aber ich verstehe nicht, wie sie funktionieren. Und ich möchte keinen Code verwenden, den ich in meinem Projekt nicht verstehe. Ich weiß, was die grundlegenden Bitoperationen sind (Verschiebungen, ANDs, ODERs usw.), aber ich verstehe nicht, wie diese Assemblierung von Operationen das tut, was sie tun.

Vielen Dank für das Betrachten dieser Frage und hoffentlich in der Lage, mir zu helfen.

Answer 1

Die 64-Bit-Integer value als dargestellt wird 8-mal-8-Block - lassen Sie uns so tun, als wir den „Inhalt“ jeder Zelle verstehen würde, wie folgt:

ist

1 2 3 4 5 6 7 8 
9 10 11 12 13 14 15 16 
17 18 19 20 21 22 23 24 
25 26 27 28 29 30 31 32 
33 34 35 36 37 38 39 40 
41 42 43 44 45 46 47 48 
49 50 51 52 53 54 55 56 
57 58 59 60 61 62 63 64 

obwohl value tatsächlich gespeichert sequentiell als

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ... 

Wir sagen auch, dass es auf der linken Seite durch vier (value << 4) Ergebnisse in

Verschiebung

5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ... 

oder

5 6 7 8 9 10 11 12 
13 14 15 16 17 18 19 20 ... 

und nach rechts von vier (value >> 4) Verschiebung gibt

0 0 0 0 1 2 3 4 
    5 6 7 8 9 10 11 12 ... 

Jetzt werfen wir

uint64 reflect_vert (uint64 value) 
{ 
    value = ((value & 0xFFFFFFFF00000000ull) >> 32) | ((value & 0x00000000FFFFFFFFull) << 32); 
    value = ((value & 0xFFFF0000FFFF0000ull) >> 16) | ((value & 0x0000FFFF0000FFFFull) << 16); 
    value = ((value & 0xFF00FF00FF00FF00ull) >> 8) | ((value & 0x00FF00FF00FF00FFull) << 8); 
    return value; 
} 

Hier sind die 0xFFFFFFFF00000000ull -ähnlichen Stücke Bit Masken, die in Kombination mit der UND-Verknüpfung Bits aus value auswählen. Beachten Sie auch, dass 0xFF entspricht einem Byte mit acht Bits gesetzt, so 0xFFFFFFFF effektiv beschreibt 4*8=32 ausgewählte Bits. Da jede Zeile 8 Bits lang ist, entspricht dies 4 Zeilen.

Konkret value & 0xFFFFFFFF00000000ull wählt (hält!) Die oberen 32 Bits von value, das heißt die ersten vier Reihen, und der Rest verworfen, während value & 0x00000000FFFFFFFFull die unteren 32 Bits wählt und verwirft die erste.

Die Verschiebungen Operationen in

((value & 0xFFFFFFFF00000000ull) >> 32) 
((value & 0x00000000FFFFFFFFull) << 32) 

dann diese Bits nach unten bewegen, entweder (>> 32) auf die Lage der unteren 32 Bits oder nach oben (<< 32). Durch ODER-Verknüpfung zusammen,

value = ((value & 0xFFFFFFFF00000000ull) >> 32) | ((value & 0x00000000FFFFFFFFull) << 32); 

Sie haben sie effektiv ausgetauscht.Nun, da die unteren 32 Bits auf die „untere Hälfte“ des Blocks entsprechen, wir tauschen nur die Zeilen wie folgt:

33 34 35 36 37 38 39 40 \ 
41 42 43 44 45 46 47 48 |__ 
49 50 51 52 53 54 55 56 | | 
57 58 59 60 61 62 63 64/| 
1 2 3 4 5 6 7 8 \ | 
9 10 11 12 13 14 15 16 |__| 
17 18 19 20 21 22 23 24 | 
25 26 27 28 29 30 31 32/

Durchführen der gleichen mit 0xFFFF0000FFFF0000ull und 0x0000FFFF0000FFFFull, mit Verschiebungen der Breite 16 Swaps zwei Reihen mit je ihre Nachbarn:

49 50 51 52 53 54 55 56 \__ 
57 58 59 60 61 62 63 64/| 
33 34 35 36 37 38 39 40 \__| 
41 42 43 44 45 46 47 48/
17 18 19 20 21 22 23 24 \__ 
25 26 27 28 29 30 31 32/| 
1 2 3 4 5 6 7 8 \__| 
9 10 11 12 13 14 15 16/

Schließlich 0xFF00FF00FF00FF00ull und 0x00FF00FF00FF00FFull mit Verschiebungen von 8 Swap jede zweite Zeile, was zu

57 58 59 60 61 62 63 64 _ 
49 50 51 52 53 54 55 56 
41 42 43 44 45 46 47 48 _ 
33 34 35 36 37 38 39 40 
25 26 27 28 29 30 31 32 _ 
17 18 19 20 21 22 23 24 
9 10 11 12 13 14 15 16 _ 
1 2 3 4 5 6 7 8 

An diesem Punkt wurde der Block erfolgreich vertikal gekippt.

Die reflect_diag Methode verwendet den gleichen Ansatz, um Bits selektiv auszutauschen. Das, was hier zu beachten ist, dass 0x0100000000000000 wählt die acht höchste (obere Reihe, links von der Mitte) Bit:

0000 0001 0000 0000 
0000 0000 0000 0000 
0000 0000 0000 0000 
0000 0000 0000 0000 

während 0x0000000000000080 wählt die acht niedrigsten (untere Reihe, rechts von der Mitte)

0000 0000 0000 0000 
0000 0000 0000 0000 
0000 0000 0000 0000 
0000 0000 1000 0000 

Bit. Sie sind genau 49 Bits auseinander, so verschiebt sie um 49 ihren Standort.

Für ein anderes Beispiel wählt das Muster 0x4020100804020100 Die Bits

0100 0000 0010 0000 
0001 0000 0000 1000 
0000 0100 0000 0010 
0000 0001 0000 0000 

während sein Gegenstück 0x0080402010080402

0000 0000 1000 0000 
0100 0000 0010 0000 
0001 0000 0000 1000 
0000 0100 0000 0010 

wählt Sie werden bemerken, dass die Abstände zwischen den Bits ein Muster bilden, das die ganze ermöglicht Block so verschoben werden, dass sie sich mit der ursprünglichen Position des anderen ausrichten.

Beachten Sie auch, dass dieser Code im Vergleich zu den horizontal und vertikal umgedrehten Versionen die ursprünglichen Werte nicht überschreibt, sondern eine neue Ausgabe erstellt. Michiels Code macht die Verschiebung in-Place und codiert die Verschiebungen in oktalen, also bedeutet >> 010 eigentlich >> 8, 020 ist 16 und so weiter.