Bitweiser Betrieb und Nutzung

Betrachten Sie diesen Code:

x = 1 # 0001 x << 2 # Shift left 2 bits: 0100 # Result: 4 x | 2 # Bitwise OR: 0011 # Result: 3 x & 1 # Bitwise AND: 0001 # Result: 1 

Ich kann die arithmetischen Operatoren in Python (und anderen Sprachen) verstehen, aber “bitweise” Operatoren habe ich nie ganz verstanden. Im obigen Beispiel (aus einem Python-Buch) verstehe ich die Linksverschiebung, aber nicht die anderen beiden.

Wofür werden bitweise Operatoren tatsächlich verwendet? Ich würde mich über einige Beispiele freuen.

Bitweise Operatoren sind Operatoren, die an Multi-Bit-Werten arbeiten, aber konzeptuell jeweils ein Bit.

  • AND ist nur 1, wenn beide Eingänge 1 sind, sonst ist es 0.
  • OR ist 1, wenn einer oder beide Eingänge 1 sind, andernfalls 0.
  • XOR ist nur 1, wenn genau einer seiner Eingänge 1 ist, sonst ist es 0.
  • NOT ist nur 1, wenn seine Eingabe 0 ist, sonst ist es 0.

Diese können oft am besten als Wahrheitstabellen gezeigt werden. Die Eingabemöglichkeiten sind oben und links, das resultierende Bit ist eins der vier (zwei im Falle von NOT, da es nur einen Eingang hat) Werte, die am Schnittpunkt der Eingänge angezeigt werden.

 AND | 0 1 OR | 0 1 XOR | 0 1 NOT | 0 1 ----+----- ---+---- ----+---- ----+---- 0 | 0 0 0 | 0 1 0 | 0 1 | 1 0 1 | 0 1 1 | 1 1 1 | 1 0 

Ein Beispiel ist, wenn Sie nur die unteren 4 Bits einer ganzen Zahl wollen, UND Sie UND es mit 15 (binäre 1111) so:

  201: 1100 1001 AND 15: 0000 1111 ------------------ IS 9 0000 1001 

Die Null-Bits in 15 wirken in diesem Fall effektiv als ein Filter, wodurch die Bits im Ergebnis ebenfalls auf Null gesetzt werden.

Außerdem sind >> und < < oft als bitweise Operatoren enthalten, und sie "verschieben" jeweils um eine bestimmte Anzahl von Bits einen Wert nach rechts und nach links, casting Bits weg, die von dem Ende, auf das Sie sich bewegen, rollen und einspeisen Null Bits am anderen Ende.

Also zum Beispiel:

 1001 0101 >> 2 gives 0010 0101 1111 1111 < < 4 gives 1111 0000 

Beachten Sie, dass die linke Verschiebung in Python insofern ungewöhnlich ist, als keine feste Breite verwendet wird, in der Bits verworfen werden. Während viele Sprachen eine feste Breite basierend auf dem Datentyp verwenden, erweitert Python die Breite einfach um zusätzliche Bits. Um das Verwerfungsverhalten in Python zu erhalten, können Sie einer Linksverschiebung mit einem bitweisen Wert folgen and beispielsweise in einem 8-Bit-Wert die vier Bits nach links verschieben:

 bits8 = (bits8 < < 4) & 255 

In diesem Sinne ist ein weiteres Beispiel für bitweise Operatoren, wenn Sie zwei 4-Bit-Werte haben, die Sie in einen 8-Bit-Wert packen möchten, können Sie alle drei Ihrer Operatoren verwenden ( left-shift and und or ):

 packed_val = ((val1 & 15) < < 4) | (val2 & 15) 
  • Die Operation & 15 sicher, dass beide Werte nur die unteren 4 Bits haben.
  • Die < < 4 ist eine 4-Bit-Verschiebung, die übrig bleibt, um val1 in die oberen 4 Bits eines 8-Bit-Wertes zu bewegen.
  • Das | verbindet diese beiden einfach miteinander.

Wenn val1 7 und val2 4 ist:

  val1 val2 ==== ==== & 15 (and) xxxx-0111 xxxx-0100 & 15 < < 4 (left) 0111-0000 | | | +-------+-------+ | | (or) 0111-0100 

Eine typische Verwendung:

| wird verwendet, um ein bestimmtes Bit auf 1 zu setzen

& wird verwendet, um ein bestimmtes Bit zu testen oder zu löschen

  • Setze ein Bit (wobei n die Bitnummer und 0 das niedrigstwertige Bit ist):

    unsigned char a |= (1 < < n);

  • Klar ein bisschen:

    unsigned char b &= ~(1 < < n);

  • Toggle ein bisschen:

    unsigned char c ^= (1 < < n);

  • Testen Sie ein bisschen:

    unsigned char e = d & (1 < < n);

Nehmen Sie den Fall Ihrer Liste zum Beispiel:

x | 2 x | 2 wird verwendet, um das Bit 1 von x auf 1 zu setzen

x & 1 wird verwendet, um zu testen, ob das Bit 0 von x 1 oder 0 ist

Wofür werden bitweise Operatoren tatsächlich verwendet? Ich würde mich über einige Beispiele freuen.

Eine der häufigsten Anwendungen bitweiser Operationen ist das Parsen von hexadezimalen colors.

Zum Beispiel ist hier eine Python- function, die einen String wie #FF09BE akzeptiert und ein Tupel ihrer Rot-, Grün- und #FF09BE zurückgibt.

 def hexToRgb(value): # Convert string to hexadecimal number (base 16) num = (int(value.lstrip("#"), 16)) # Shift 16 bits to the right, and then binary AND to obtain 8 bits representing red r = ((num >> 16) & 0xFF) # Shift 8 bits to the right, and then binary AND to obtain 8 bits representing green g = ((num >> 8) & 0xFF) # Simply binary AND to obtain 8 bits representing blue b = (num & 0xFF) return (r, g, b) 

Ich weiß, dass es effizientere Wege gibt, dies zu erreichen, aber ich glaube, dass dies ein sehr prägnantes Beispiel ist, das sowohl Verschiebungen als auch bitweise Boolesche Operationen veranschaulicht.

Ich denke, dass der zweite Teil der Frage:

Wofür werden bitweise Operatoren tatsächlich verwendet? Ich würde mich über einige Beispiele freuen.

Wurde nur teilweise angesprochen. Das sind meine zwei Cent in dieser Angelegenheit.

Bitwise-Operationen in Programmiersprachen spielen eine grundlegende Rolle im Umgang mit vielen Anwendungen. Fast alle Low-Level-Computing muss mit dieser Art von Operationen durchgeführt werden.

In allen Anwendungen, die Daten zwischen zwei Knoten senden müssen, z.

  • Computernetzwerke;

  • Telekommunikationsanwendungen (Mobiltelefone, Satellitenkommunikation usw.).

In der unteren Schicht der Kommunikation werden die Daten normalerweise in sogenannten Rahmen gesendet. Frames sind nur Bytefolgen, die über einen physischen Kanal gesendet werden. Diese Rahmen enthalten normalerweise die tatsächlichen Daten plus einige andere Felder (in Bytes codiert), die Teil des so genannten Headers sind . Der Header enthält normalerweise Bytes, die einige Informationen kodieren, die sich auf den Status der Kommunikation beziehen (z. B. mit Flags (Bits)), Frame-Zähler, Korrektur- und Fehlererkennungscodes usw. Um die übertragenen Daten in einem Frame zu erhalten und den Frames, um Daten zu senden, werden Sie für bestimmte bitweise Operationen benötigen.

Im Allgemeinen steht bei solchen Anwendungen eine API zur Verfügung, sodass Sie nicht mit all diesen Details fertig werden müssen. Zum Beispiel stellen alle modernen Programmiersprachen Bibliotheken für Socket-Verbindungen bereit, sodass Sie die TCP / IP-Kommunikationsrahmen nicht wirklich erstellen müssen. Aber denken Sie an die guten Leute, die diese APIs für Sie programmiert haben, sie mussten sich mit der Frame-Konstruktion sicher befassen; Verwenden aller Arten von bitweisen Operationen, um von der Low-Level- zur High-Level-Kommunikation hin und her zu gehen.

Stellen Sie sich vor, Sie erhalten eine Datei, die Rohdaten enthält, die direkt von der Telekommunikationshardware erfasst wurden. In diesem Fall müssen Sie, um die Frames zu finden, die rohen Bytes in der Datei lesen und versuchen, eine Art von Synchronisationswörtern zu finden, indem Sie die Daten bitweise abtasten. Nachdem Sie die Synchronisationswörter identifiziert haben, müssen Sie die tatsächlichen Frames abrufen und sie ggf. verschieben (und das ist nur der Anfang der Story), um die tatsächlichen Daten zu erhalten, die übertragen werden.

Eine weitere sehr unterschiedliche Low-Level-Familie von Anwendungen ist, wenn Sie Hardware mit einigen (Art von alten) Ports, wie parallelen und seriellen Ports steuern müssen. Diese Ports werden gesteuert, indem einige Bytes gesetzt werden, und jedes Bit dieser Bytes hat eine spezifische Bedeutung in Bezug auf statementen für diesen Port (siehe zum Beispiel http://en.wikipedia.org/wiki/Parallel_port ). Wenn Sie Software erstellen möchten, die etwas mit dieser Hardware macht, benötigen Sie bitweise Operationen, um die statementen, die Sie ausführen möchten, in die Bytes zu übersetzen, die der Port versteht.

Wenn Sie zum Beispiel einige physische Tasten an den parallelen Anschluss angeschlossen haben, um ein anderes Gerät zu steuern, ist dies eine Codezeile, die Sie in der Soft-Anwendung finden können:

 read = ((read ^ 0x80) >> 4) & 0x0f; 

Hoffe das trägt dazu bei.

Ich hoffe, dies verdeutlicht diese beiden:

 x | 2 0001 //x 0010 //2 0011 //result = 3 

 x & 1 0001 //x 0001 //1 0001 //result = 1 

Stellen Sie sich 0 als falsch und 1 als wahr vor. Dann arbeiten bitweise und (&) und oder (|) genau wie regulär und und oder außer sie machen alle Bits in dem Wert auf einmal. In der Regel werden sie für Flags verwendet, wenn Sie 30 Optionen haben, die gesetzt werden können (z. B. als Zeichnungsstile in einem Fenster). Sie möchten nicht 30 separate boolesche Werte übergeben, um sie einzeln zu setzen oder zu löschen um Optionen zu einem einzelnen Wert zu kombinieren und dann mit & prüfen, ob jede Option gesetzt ist. Diese Art der Flag-Weitergabe wird von OpenGL stark genutzt. Da jedes Bit ein separates Flag ist, erhalten Sie Flag-Werte für Potenzen von zwei (auch bekannt als Zahlen, die nur ein Bit gesetzt haben) 1 (2 ^ 0) 2 (2 ^ 1) 4 (2 ^ 2) 8 (2 ^ 3) power of two teilt Ihnen mit, welches Bit gesetzt ist, wenn das Flag gesetzt ist.

Beachten Sie auch 2 = 10, also x | 2 ist 110 (6) nicht 111 (7) Wenn keines der Bits überlappen (was in diesem Fall gilt) | wirkt wie Zugabe.

Ich habe es oben nicht erwähnt, aber Sie werden auch sehen, dass einige Leute die linke und rechte Verschiebung für arithmetische Operationen verwenden. Eine Verschiebung nach links um x entspricht der Multiplikation mit 2 ^ x (solange sie nicht überläuft) und eine Verschiebung nach rechts entspricht der Division durch 2 ^ x.

Vor kurzem habe ich Leute gesehen, die x < < 1 und x >> 1 zum Verdoppeln und Halbieren verwenden, obwohl ich nicht sicher bin, ob sie nur versuchen, clever zu sein oder ob es wirklich einen deutlichen Vorteil gegenüber den normalen Operatoren gibt.

In diesem Beispiel werden die Operationen für alle vier 2-Bit-Werte angezeigt:

 10 | 12 1010 #decimal 10 1100 #decimal 12 1110 #result = 14 

 10 & 12 1010 #decimal 10 1100 #decimal 12 1000 #result = 8 

Hier ist ein Anwendungsbeispiel:

 x = raw_input('Enter a number:') print 'x is %s.' % ('even', 'odd')[x&1] 

Ein weiterer häufiger Anwendungsfall ist das Bearbeiten / Testen von Dateiberechtigungen. Siehe das Python stat-Modul: http://docs.python.org/library/stat.html .

Um beispielsweise die Berechtigungen einer Datei mit einem gewünschten Berechtigungssatz zu vergleichen, können Sie Folgendes tun:

 import os import stat #Get the actual mode of a file mode = os.stat('file.txt').st_mode #File should be a regular file, readable and writable by its owner #Each permission value has a single 'on' bit. Use bitwise or to combine #them. desired_mode = stat.S_IFREG|stat.S_IRUSR|stat.S_IWUSR #check for exact match: mode == desired_mode #check for at least one bit matching: bool(mode & desired_mode) #check for at least one bit 'on' in one, and not in the other: bool(mode ^ desired_mode) #check that all bits from desired_mode are set in mode, but I don't care about # other bits. not bool((mode^desired_mode)&desired_mode) 

Ich werfe die Ergebnisse als Booleans aus, weil ich mich nur für die Wahrheit oder Falschheit interessiere, aber es wäre eine lohnende Übung, die bin () – Werte für jeden auszudrucken.

Bit-Repräsentationen von Ganzzahlen werden häufig beim wissenschaftlichen Rechnen verwendet, um Arrays von Wahr-Falsch-Informationen darzustellen, da eine bitweise Operation viel schneller ist als das Iterieren durch ein Array von Booleschen Werten. (Höherwertige Sprachen können die Idee eines Bit-Arrays verwenden.)

Ein schönes und ziemlich einfaches Beispiel hierfür ist die allgemeine Lösung des Spiels von Nim. Sehen Sie sich den Python- Code auf der Wikipedia-Seite an . Es verwendet stark bitweise exklusiv oder, ^ .

Es gibt möglicherweise einen besseren Weg zu finden, wo ein Array-Element zwischen zwei Werten ist, aber wie in diesem Beispiel gezeigt wird, funktioniert & hier, während und nicht.

 import numpy as np a=np.array([1.2, 2.3, 3.4]) np.where((a>2) and (a<3)) #Result: Value Error np.where((a>2) & (a<3)) #Result: (array([1]),) 

Ich habe es nicht erwähnt, Dieses Beispiel zeigt Ihnen die Dezimaloperation (-) für 2-Bit-Werte: AB (nur wenn A B enthält)

Diese Operation wird benötigt, wenn wir in unserem Programm ein Verb halten, das Bits repräsentiert. manchmal müssen wir Bits hinzufügen (wie oben) und manchmal müssen wir Bits entfernen (wenn das Verb dann enthält)

 111 #decimal 7 - 100 #decimal 4 -------------- 011 #decimal 3 

mit Python: 7 & ~ 4 = 3 (entferne von 7 die Bits, die 4 darstellen)

 001 #decimal 1 - 100 #decimal 4 -------------- 001 #decimal 1 

mit python: 1 & ~ 4 = 1 (entferne von 1 die Bits, die 4 darstellen – in diesem Fall ist 1 nicht ‘enthält’ 4) ..

Während das Manipulieren von Bits einer ganzen Zahl nützlich ist, kann oft für Netzwerkprotokolle, die bis auf das Bit spezifiziert werden können, die Manipulation längerer Bytefolgen (die nicht einfach in eine ganze Zahl umgewandelt werden können) erforderlich sein. In diesem Fall ist es nützlich, die Bitstring- Bibliothek zu verwenden, die bitweise Operationen an Daten ermöglicht – zB kann man die Zeichenkette ‘ABCDEFGHIJKLMNOPQ’ als String oder als Hex- und Bit-Shift importieren (oder andere bitweise Operationen ausführen):

 >>> import bitstring >>> bitstring.BitArray(bytes='ABCDEFGHIJKLMNOPQ') < < 4 BitArray('0x142434445464748494a4b4c4d4e4f50510') >>> bitstring.BitArray(hex='0x4142434445464748494a4b4c4d4e4f5051') < < 4 BitArray('0x142434445464748494a4b4c4d4e4f50510') 

Sätze

Sätze können mit mathematischen Operationen kombiniert werden.

  • Der Union Operator | kombiniert zwei Sätze, um einen neuen zu bilden, der Elemente in beiden enthält.
  • Der Kreuzungsoperator & erhält nur Artikel in beiden.
  • Der Differenzoperator - erhält Elemente in der ersten Menge, aber nicht in der zweiten Menge.
  • Der symmetrische Differenzoperator ^ erhält Elemente in beiden Mengen, aber nicht beide.

Versuch es selber:

 first = {1, 2, 3, 4, 5, 6} second = {4, 5, 6, 7, 8, 9} print(first | second) print(first & second) print(first - second) print(second - first) print(first ^ second) 

Ergebnis:

 {1, 2, 3, 4, 5, 6, 7, 8, 9} {4, 5, 6} {1, 2, 3} {8, 9, 7} {1, 2, 3, 7, 8, 9} 

die folgenden bitweisen Operatoren: & , | , ^ und ~ liefern Werte (basierend auf ihrer Eingabe) auf die gleiche Weise, wie logische Gatter Signale beeinflussen. Sie könnten sie verwenden, um Schaltungen zu emulieren.