Python Bit Arithmetic Super Einführung
In diesem Abschnitt werden die Grundlagen von Bitoperationen beschrieben, die an Binärzahlen ausgeführt werden. Python wird zur Erklärung verwendet.
Binärzahl
Beschreibe mit 0b. Wenn Sie es in REPL eingeben, wird es in eine Dezimalzahl konvertiert.
>>> 0b101
5
Verwenden Sie bin (), um in binär zu konvertieren.
>>> bin(5)
'0b101'
Hexadezimal
Sie können von hexadezimal nach binär konvertieren, indem Sie die ursprüngliche Zahl hexadezimal schreiben.
>>> bin(0x12)
'0b10010'
Verwenden Sie hex (), um in hexadezimal zu konvertieren.
>>> hex(0b10010)
'0x12'
Verschiebung
Verschieben Sie die Ziffern. Je nach Richtung gibt es Links- und Rechtsverschiebungen.
Linksverschiebung
Der Operator <<. Verschiebt die angegebene Ziffer nach links und 0 wird in das freie Bit eingegeben.
Ein Beispiel wird mit der richtigen Begründung gezeigt.
| Eingabe | Ausgabe |
|---|---|
| bin(5<<0) | '0b101' |
| bin(5<<1) | '0b1010' |
| bin(5<<2) | '0b10100' |
| bin(5<<3) | '0b101000' |
Nach rechts verschieben
Der Operator >>. Verschiebt die angegebene Ziffer nach rechts und die vor der niedrigsten Ordnung extrudierten Bits verschwinden.
Ein Beispiel wird mit der richtigen Begründung gezeigt.
| Eingabe | Ausgabe |
|---|---|
| bin(5>>0) | '0b101' |
| bin(5>>1) | '0b10' |
| bin(5>>2) | '0b1' |
| bin(5>>3) | '0b0' |
Logische Operation
Es ist eine Berechnung für jede Ziffer der Binärzahl.
Die Grundidee ist die Verarbeitung mit booleschen Werten, wobei 1 als wahr und 0 als falsch betrachtet wird.
Logisches Produkt (UND)
Der Operator &. Gilt nur (1), wenn ** beide ** wahr sind (1). Wenn Sie nur eine Ziffer betrachten, entspricht dies der Multiplikation.
| AND | Multiplikation | Ergebnis |
|---|---|---|
| 0 & 0 | 0 * 0 | 0 |
| 0 & 1 | 0 * 1 | 0 |
| 1 & 0 | 1 * 0 | 0 |
| 1 & 1 | 1 * 1 | 1 |
Bei mehreren Ziffern wird jede Ziffer unabhängig multipliziert, ohne dass ein Übertrag berücksichtigt wird.
10010010
&) 10100111
-----------
10000010
Fragen Sie bei Python nach.
>>> bin(0b10010010 & 0b10100111)
'0b10000010'
Logische Summe (ODER)
Der Operator |. Wenn eines der beiden ** wahr ist (1), gilt es (1). Wenn Sie nur eine Ziffer betrachten, ähnelt dies der Addition, aber alle 1 oder mehr des Berechnungsergebnisses werden als 1 (2 → 1) behandelt.
| OR | Zusatz | Ergebnis |
|---|---|---|
| 0 | 0 | 0 + 0 | 0 |
| 0 | 1 | 0 + 1 | 1 |
| 1 | 0 | 1 + 0 | 1 |
| 1 | 1 | 1 + 1 | 2→1 |
Fügen Sie für mehrere Ziffern jede Ziffer unabhängig hinzu, ohne einen Übertrag zu berücksichtigen. Alle 1 oder mehr Berechnungsergebnisse werden als 1 (2 → 1) behandelt.
10010010
|) 10100111
-----------
10110111
Fragen Sie bei Python nach.
>>> bin(0b10010010 | 0b10100111)
'0b10110111'
Exklusive logische Summe (XOR)
Der Operator ^. Wenn ** nur einer ** wahr ist (1), gilt (1) (der inkompatible Punkt ist ** exklusiv **). Wenn Sie nur eine Binärziffer betrachten, wird der Übertrag durch einen Zusatz verworfen (1 + 1 = 2 = 0b10 → 0).
| XOR | Zusatz | Ergebnis |
|---|---|---|
| 0 ^ 0 | 0 + 0 | 0 |
| 0 ^ 1 | 0 + 1 | 1 |
| 1 ^ 0 | 1 + 0 | 1 |
| 1 ^ 1 | 1 + 1 | 2→0 |
Fügen Sie für mehrere Ziffern jede Ziffer unabhängig hinzu, ohne einen Übertrag zu berücksichtigen.
10010010
^) 10100111
-----------
00110101
Fragen Sie bei Python nach.
>>> bin(0b10010010 ^ 0b10100111)
'0b110101'
Es hat die Eigenschaft, dass, wenn Sie XOR zweimal mit demselben Wert ausführen, der ursprüngliche Wert wiederhergestellt wird.
a ^ b ^ b→a
>>> bin(0b10010010 ^ 0b10100111 ^ 0b10100111)
'0b10010010'
Sie können auch den ursprünglichen Wert löschen.
a ^ b ^ a→b
>>> bin(0b10010010 ^ 0b10100111 ^ 0b10010010)
'0b10100111'
Invertieren (NICHT)
Der Operator ~. 0 und 1 umkehren.
Python betrachtet die obere Ziffer als unendlich mit Nullen gefüllt, und Invertierungen geben auch ein Minus zurück, vorausgesetzt, die obere Ziffer ist unendlich mit 1 gefüllt.
>>> ~1
-2
Diese Berechnung bedeutet "000 ... 0001" → "111 ... 1110".
Wie wir später in der Kombination von UND und NICHT sehen werden, konzentrieren wir uns normalerweise nur auf die Bits und nicht auf die spezifischen numerischen Werte (hier minus). Wenn Sie an der Idee des Zeichens interessiert sind, lesen Sie bitte den folgenden Artikel.
-
@ 7shi: Intuitive Denkweise für signierte Zahlen 2014.10.8
-
Der Ausdruck "~ x" → "- (x + 1)" darf nur mit dem Wert eingeführt werden. Selbst wenn Sie sich das ansehen, verstehen Sie die Bedeutung der Bitinversion nicht, deshalb werde ich sie hier nicht weiter verfolgen.
Anwendungsbeispiel
Die Bitoperation wird häufig verwendet, wenn nur einige Bits extrahiert werden.
Bitmaske
Beim Extrahieren nur des erforderlichen Teils des Bits UND des erforderlichen Teils mit der auf 1 gesetzten Nummer.
Beispiel: Extrahieren Sie die unteren 3 Bits (fetter Teil) aus 101 110 </ strong>.
101110
&) 000111
---------
000110
Kombinierter Einsatz mit Schicht
Wenn Sie nur die Bits in der Mitte extrahieren möchten, verwenden Sie Shift und Mask zusammen.
Beispiel: Extrahieren Sie die mittleren 2 Bits (fetter Teil) aus 10 11 </ strong> 10.
>>> bin((0b101110 >> 2) & 0b11)
'0b11'
Kombinierte Verwendung mit NICHT
Wenn Sie NOT in Kombination mit AND verwenden, bedeutet dies, dass Sie es verwenden können, ohne sich über das negative Ergebnis von NOT Gedanken machen zu müssen.
Indem Sie das Ergebnis der NICHT-Berechnung mit UND maskieren, können Sie die Anzahl der Ziffern begrenzen und Negative entfernen.
>>> bin(~1 & 0b1111)
'0b1110'
Diese Berechnung zeigt die Inversion von "0001" → "1110", indem sie auf 4 Binärziffern begrenzt wird.
NOT wird oft verwendet, um Maskenwerte zu erstellen, und selbst in diesem Fall sind uns die Negative nicht bekannt.
Wenn Sie beispielsweise nur die zentralen 2 Bits (fetter Teil) von 10 11 </ strong> 10 löschen möchten, können Sie sich NICHT auf den Teil konzentrieren, den Sie löschen möchten.
>>> bin(0b101110 & ~0b001100)
'0b100010'
Hier ist der Code, der NICHT zum Vergleich verwendet. Ich achte auf den Teil, den ich behalten möchte.
>>> bin(0b101110 & 0b110011)
'0b100010'
Bitzusammensetzung
Wenn Sie mehrere Werte an unterschiedlichen Positionen halten möchten, verwenden Sie Shift und OR zusammen.
Beispiel: Kombinieren Sie "101" und "110" nebeneinander zu einem Wert.
>>> bin((0b101 << 3) | 0b110)
'0b101110'
Kombinierte Verwendung mit UND
Wenn sich bereits ein anderer Wert in dem Teil befindet, den Sie kombinieren möchten, löschen Sie ihn zuerst mit AND und dann mit OR.
Beispiel: Ersetzen Sie die unteren 3 Bits (fetter Teil) von 101 101 </ strong> durch 011.
101101
&) 111000
---------
101000
|) 011
---------
101011
Fragen Sie bei Python nach.
>>> bin(0b101101 & 0b111000 | 0b011)
'0b101011'
Diese Technik wird auch verwendet, um Hintergründe und Zeichen bei der Bilderzeugung zu kombinieren.
Fehler finden
Sie können XOR verwenden, um die verschiedenen Bits der beiden Zahlen anzuzeigen.
11101011101110101
^) 11101101101110101
--------------------
00000110000000000
Fragen Sie bei Python nach.
>>> bin(0b11101011101110101 ^ 0b11101101101110101)
'0b110000000000'
Werte tauschen
[Anmerkung] Dies ist eine Einführung als Wissen und nicht als Praktikabilität.
Bei der Anwendung mehrerer XOR gibt es eine Technik zum Austauschen der Werte von Variablen.
- [XOR-Austauschalgorithmus-Wikipedia](http://ja.wikipedia.org/wiki/XOR%E4%BA%A4%E6%8F%9B%E3%82%A2%E3%83%AB%E3%82 % B4% E3% 83% AA% E3% 82% BA% E3% 83% A0)
Fragen Sie bei Python nach.
>>> a = 12
>>> b = 34
>>> a, b
(12, 34)
>>> a = a ^ b
>>> b = a ^ b
>>> a = a ^ b
>>> a, b
(34, 12)
Praktisch ist es einfacher, Tapple zu verwenden.
>>> a, b = b, a
Beziehung zur Berechnung
Eine Art von Berechnung kann die Bitoperation ersetzen. Hier sind einige häufig verwendete.
Multiplikation
Binärzahlen verdoppeln sich, wenn die Ziffern steigen.
| Binärzahl | Dezimalzahl | Linksverschiebung | Berechnung |
|---|---|---|---|
| 0b1 | 1 | 1 << 0 | |
| 0b10 | 2 | 1 << 1 | |
| 0b100 | 4 | 1 << 2 | |
| 0b1000 | 8 | 1 << 3 |
Das heißt, 1 << n ist gleich $ 2 ^ n $.
Jedes Mal, wenn Sie eine Zahl um 1 Bit nach links verschieben, wird sie verdoppelt.
| Linksverschiebung | Multiplikation | Ausgabe |
|---|---|---|
| bin(5<<0) | bin(5) | '0b101' |
| bin(5<<1) | bin(5*2) | '0b1010' |
| bin(5<<2) | bin(522) | '0b10100' |
| bin(5<<3) | bin(522*2) | '0b101000' |
Mit anderen Worten, "n-Bit-Linksverschiebung" hat das gleiche Ergebnis wie "Multiplikation von $ 2 ^ n $".
Teilung
In der entgegengesetzten Theorie hat "n-Bit-Rechtsverschiebung" das gleiche Ergebnis wie "$ 2 ^ n $ Division (Kürzung)".
| Nach rechts verschieben | Teilung | Ausgabe |
|---|---|---|
| bin(45>>0) | bin(45) | '0b101101' |
| bin(45>>1) | bin(45/2) | '0b10110' |
| bin(45>>2) | bin(45/2/2) | '0b1011' |
| bin(45>>3) | bin(45/2/2/2) | '0b101' |
Rest der Teilung
"Der Rest der Division durch $ 2 ^ n $" ist gleich "UND mit $ 2 ^ n-1 $".
x % (2 ** n)==x & ((2 ** n) - 1)
Beispiel: x% 8 == x & 7
Erläuterung
Ich werde den Grund erklären, warum dies so intuitiv wie möglich ist.
Das Verschieben von "0b110101" nach rechts um 3 Bits entspricht dem Teilen durch $ 2 ^ 3 = 8 $ und dem Abschneiden.
>>> bin(0b110101 >> 3)
'0b110'
>>> bin(0b110101 / 8)
'0b110'
Die unteren 3 Bits "101", die zu diesem Zeitpunkt durch die Verschiebung extrudiert wurden, entsprechen dem Rest der Division. Sie können es abrufen, indem Sie es mit 111 maskieren.
>>> bin(0b110101 & 0b111)
'0b101'
>>> bin(0b110101 % 8)
'0b101'
"0b111" ist "7", dh "8-1". Dies bestätigte die folgende Beziehung.
x % 8==x & 7
Abwertung
"Untere n Bits löschen" entspricht "Abwertung bei $ 2 ^ n $".
Als Beispiel wird die Abwertung bei $ 2 ^ 3 = 8 $ aufgrund der Verschiebung gezeigt. Durch die Rechtsverschiebung werden die unteren 3 Bits herausgedrückt, und durch die Linksverschiebung wird die ursprüngliche Bitbreite wiederhergestellt.
>>> 15 >> 3 << 3
8
>>> 16 >> 3 << 3
16
>>> 17 >> 3 << 3
16
Es ist auch möglich, ein bestimmtes Bit mit einer Kombination aus AND und NOT zu löschen. Es mag zunächst verwirrend erscheinen, aber diese Methode wird häufiger verwendet als Schichten.
>>> 15 & ~0b111
8
>>> 16 & ~0b111
16
>>> 17 & ~0b111
16
"0b111" ist "7", dh "8-1". Dies ist eine Beziehung, die sich auch in der Methode gezeigt hat, den Rest zu finden, den wir zuvor gesehen haben.
Unter Verwendung der Beziehung "~ 7" → "-8" kann die Abwertung bei 8 durch -8 ausgedrückt werden.
>>> 15 & -8
8
>>> 16 & -8
16
>>> 17 & -8
16
Wenn Sie dies zum ersten Mal sehen, verstehen Sie es möglicherweise nicht. Vorerst muss man nur erkennen, dass "es manchmal in einem solchen Ausdruck geschrieben ist".
Recommended Posts