Anwendungen von bitweisen Operatoren in C und ihre Effizienz? [Duplikat]
Ich bin neu für bitweise Operatoren.
Ich verstehe, wie die Logik funktioniert, um das Endergebnis zu erhalten. Wenn Sie beispielsweise bitweise AND zwei Zahlen eingeben, wird das Endergebnis AND dieser beiden Zahlen sein ( 1 & 0 = 0 ; 1 & 1 = 1 ; 0 & 0 = 0 ). Gleiches mit OR , XOR und NOT .
Was ich nicht verstehe, ist ihre Anwendung. Ich habe versucht, überall hinzuschauen, und die meisten erklären nur, wie bitweise Operationen funktionieren. Von allen bitweisen Operatoren verstehe ich nur die Anwendung von Shift-Operatoren (Multiplikation und Division). Ich bin auch auf Maskierung gestoßen. Ich verstehe, dass das Maskieren mit bitweisem AND durchgeführt wird, aber was genau ist sein Zweck und wo und wie kann ich es verwenden?
Können Sie näher erläutern, wie ich Maskierung verwenden kann? Gibt es ähnliche Verwendungen für OR und XOR ?
6 Antworten
Der Low-Level-Anwendungsfall für die bitweisen Operatoren ist das Ausführen von Base-2-Berechnungen. Es gibt den bekannten Trick, um zu testen, ob eine Zahl eine Potenz von 2 ist:
%Vor%Aber es kann auch eine höhere Funktion erfüllen: Manipulation einstellen. Sie können denken, wenn eine Sammlung von Bits als Set. Um zu erklären, lasst jedes Bit in einem Byte 8 verschiedene Gegenstände repräsentieren, sagen die Planeten in unserem Sonnensystem (Pluto wird nicht länger als Planet betrachtet, also ist 8 genug!):
%Vor% Dann können wir eine Sammlung von Planeten (eine Teilmenge) wie zum Beispiel | :
Nun können Sie mit & testen, ob zwei Sätze einen Schnittpunkt haben:
Die Operation ^ wird oft verwendet, um zu sehen, was sich zwischen zwei Mengen unterscheidet (die Vereinigung der Mengen minus ihrer Schnittmenge):
Denken Sie also an | als Union, & als Schnittmenge und ^ als Union minus Schnittpunkt.
Sobald Sie sich mit der Idee von Bits beschäftigt haben, die eine Menge darstellen, sind die bitweisen Operationen natürlich da, um diese Mengen zu manipulieren.
Eine Anwendung von bitweisen UNDs prüft, ob ein einzelnes Bit in einem Byte gesetzt ist. Dies ist nützlich in der vernetzten Kommunikation, wo Protokoll-Header versuchen, so viel Information wie möglich in den kleinsten Bereich zu packen, um den Overhead zu reduzieren.
Zum Beispiel verwendet der IPv4-Header die ersten drei Bits des sechsten Bytes, um zu bestimmen, ob das gegebene IP-Paket fragmentiert werden kann, und wenn ja, ob weitere Fragmente des gegebenen Pakets folgen sollen. Wenn diese Felder stattdessen die Größe von Ints (1 Byte) hätten, wäre jedes IP-Paket 21 Bit größer als notwendig. Dies führt jeden Tag zu einer großen Menge unnötiger Daten über das Internet.
Um diese 3 Bits abzurufen, kann ein bitweises AND neben einer Bitmaske verwendet werden, um festzustellen, ob sie gesetzt sind.
%Vor%Kleine Sets, wie schon erwähnt. Sie können eine überraschend große Anzahl von Operationen schnell durchführen, Schnittpunkt und Vereinigung und (symmetrische) Differenz sind offensichtlich trivial, aber Sie können zum Beispiel auch effizient:
- Erhalte den niedrigsten Gegenstand im Set mit
x & -x - Entferne den niedrigsten Gegenstand aus dem Set mit
x & (x - 1) - füge alle Elemente hinzu, die kleiner sind als das kleinste vorhandene Element
- füge alle Gegenstände hinzu, die höher sind als der kleinste anwesende Gegenstand
- berechnet ihre Kardinalität (obwohl der Algorithmus nicht trivial ist)
- Permutieren Sie die Menge in gewisser Weise, dh ändern Sie die Indizes der Elemente (nicht alle Permutationen sind gleich effizient)
- Berechne den lexikografisch nächsten Satz, der so viele Gegenstände enthält (Gospers Hack)
1 und 2 und ihre Variationen können verwendet werden, um effiziente Graphalgorithmen in kleinen Graphen zu erstellen, siehe z. B. Algorithmus R in der Kunst der Computerprogrammierung 4A.
Andere Anwendungen von bitweisen Operationen umfassen, sind aber nicht beschränkt auf
- Bitboards, wichtig in vielen Brettspielen. Schach ohne Bitboards ist wie Weihnachten ohne Weihnachtsmann. Es ist nicht nur eine platzsparende Darstellung, Sie können nicht-triviale Berechnungen direkt mit dem Bitboard durchführen (siehe Hyperbola Quintessence)
- seitwärts Heaps und ihre Anwendung bei der Suche nach dem nächstgelegenen gemeinsamen Vorfahren und Computerbereich Mindestabfragen.
- effiziente Zyklusdetektion (Gospers Loop Detection, gefunden in HAKMEM)
- Hinzufügen von Offsets zu Z-Kurven-Adressen, ohne sie zu dekonstruieren und zu rekonstruieren (siehe Tesseral Arithmetic)
Diese Anwendungen sind mächtiger, aber auch fortgeschritten, selten und sehr spezifisch. Sie zeigen jedoch, dass bitweise Operationen nicht nur ein niedliches Spielzeug aus den alten Low-Level-Tagen sind.
Beispiel 1
Wenn Sie 10 Booleans haben, die "zusammenarbeiten", können Sie Ihren Code sehr vereinfachen.
%Vor%Beispiel 2
Schnittstellen mit Hardware. Eine Adresse auf der Hardware benötigt möglicherweise Zugriff auf Bit-Ebene, um die Schnittstelle zu steuern. z.B. ein Überlauf-Bit in einem Puffer oder ein Status-Byte, das Ihnen den Status von 8 verschiedenen Dingen mitteilen kann. Mit Bit-Maskierung können Sie das eigentliche Bit der Informationen erhalten, die Sie brauchen.
%Vor%Dies ist wirklich nur ein Spezialfall von Beispiel 1.
Bitweise Operatoren sind besonders nützlich in Systemen mit begrenzten Ressourcen, da jedes Bit einen booleschen Wert codieren kann. Die Verwendung vieler Zeichen für Flags ist verschwenderisch, da jedes ein Byte Speicherplatz benötigt (wenn sie jeweils 8 Flags speichern könnten).
Üblicherweise haben Mikrocontroller C-Schnittstellen für ihre IO-Ports, in denen jedes Bit einen von acht Ports steuert. Ohne bitweise Operatoren wären diese ziemlich schwer zu kontrollieren.
Bezüglich der Maskierung ist es üblich, sowohl & amp; und |:
%Vor%
Tags und Links c bitwise-operators masking