Eine bitwise Operation funktioniert auf einem oder mehr Bit-Mustern oder binären Ziffern am Niveau ihrer individuellen Bit. Es ist eine schnelle, primitive Handlung, die direkt durch den Verarbeiter unterstützt ist und wird verwendet, um Werte für Vergleiche und Berechnungen zu manipulieren.

Auf einfachen preisgünstigen Verarbeitern, normalerweise, bitwise Operationen sind wesentlich schneller als Abteilung, mehrere Male schneller als Multiplikation, und manchmal bedeutsam schneller als Hinzufügung. Während moderne Hochleistungsverarbeiter gewöhnlich Hinzufügung und Multiplikation so schnell wie bitwise Operationen durchführen, können die Letzteren noch für die gesamte Macht/Leistung optimal sein, die erwartet ist, Quellengebrauch zu senken.

Maschinenbediener von Bitwise

Bemerken Sie, dass in den Erklärungen unten jede Anzeige einer Position eines Bit von der richtigen (am wenigsten bedeutenden) Seite aufgezählt wird, verlassen vorwärts gehend. Zum Beispiel hat der binäre Wert 0001 (dezimaler 1) zeroes an jeder Position, aber der ersten.

NICHT

Der bitwise NICHT, oder Ergänzung, ist eine unäre Operation, die logische Ablehnung auf jedem Bit durchführt, ergänzt das Bilden von denjenigen vom gegebenen binären Wert. Bit, die 0 sind, werden 1, und diejenigen, die 1 sind, werden 0. Zum Beispiel:

NICHT 0111 (dezimale 7)

= 1000 (Dezimalzahl 8)

Die bitwise Ergänzung ist der Ergänzung des two des Werts minus einer gleich. Wenn die Ergänzungsarithmetik von two, dann verwendet wird

:NOT x = x  1.

Für nicht unterzeichnete ganze Zahlen ist die bitwise Ergänzung einer Zahl das "Spiegelnachdenken" der Zahl über den Punkt auf halbem Weg der Reihe der nicht unterzeichneten ganzen Zahl. Zum Beispiel, für nicht unterzeichnete ganze 8-Bit-Zahlen, der auf einem Graphen als eine Linie nach unten vergegenwärtigt werden kann, die effektiv eine zunehmende Reihe von 0 bis 255, zu einer abnehmenden Reihe von 255 bis 0 "schnipst". Ein einfacher, aber veranschaulichender Beispiel-Gebrauch soll ein grayscale Image umkehren, wo jedes Pixel als eine nicht unterzeichnete ganze Zahl versorgt wird.

UND

Ein bitwise UND nimmt zwei binäre Darstellungen der gleichen Länge und führt das logische UND die Operation auf jedem Paar von entsprechenden Bit durch. Das Ergebnis in jeder Position ist 1, wenn das erste Bit 1 ist und das zweite Bit 1 ist; sonst ist das Ergebnis 0. Darin führen wir die Multiplikation von zwei Bit, d. h. 1 &#215 durch; 0 = 0 und 1 × 1 = 1. Zum Beispiel:

0101 (dezimale 5)

UND 0011 (dezimale 3)

= 0001 (dezimaler 1)

Das kann verwendet werden, um zu bestimmen, ob ein besonderes Bit (1) oder klar (0) gesetzt wird. Zum Beispiel, in Anbetracht wenig Musters 0011 (dezimale 3), um zu bestimmen, ob das zweite Bit gesetzt wird, verwenden wir einen bitwise UND mit wenig Muster, das 1 nur im zweiten Bit enthält:

0011 (dezimale 3)

UND 0010 (dezimale 2)

= 0010 (dezimale 2)

Weil das Ergebnis 0010 Nichtnull ist, wissen wir, dass das zweite Bit im ursprünglichen Muster gesetzt wurde. Das wird häufig Bit-Maskierung genannt. (Analog, der Gebrauch von Abdeckband-Deckel oder Masken, Teile, die nicht verändert werden sollten oder Teile, die nicht von Interesse sind. In diesem Fall maskieren die 0 Werte die Bit, die nicht von Interesse sind.)

Wenn wir das Ergebnis versorgen, kann das an klare ausgewählte Bit in einem Register gewöhnt sein. Angeführt das Beispiel 0110 (dezimale 6), das zweite Bit kann durch das Verwenden eines bitwise UND mit dem Muster geklärt werden, das eine Null nur im zweiten Bit hat:

0110 (dezimale 6)

UND 1101 (dezimale 13)

= 0100 (dezimale 4)

ODER

Ein bitwise ODER nimmt Zwei-Bit-Muster der gleichen Länge und führt die logische einschließliche ODER-Verknüpfung auf jedem Paar von entsprechenden Bit durch. Das Ergebnis in jeder Position ist 1, wenn das erste Bit 1 ist oder das zweite Bit 1 oder beide Bit ist, sind 1; sonst ist das Ergebnis 0. Darin führen wir die Hinzufügung von zwei Bit, d. h. 0 + 1 = 1, jedoch 1 + 1 = 1 durch. Zum Beispiel:

0101 (dezimale 5)

ODER 0011 (dezimale 3)

= 0111 (dezimale 7)

Der bitwise ODER kann verwendet werden, um ausgewählte Bit, wie ein spezifisches Bit (oder Fahne) in einem Register zu setzen, wo jedes Bit den individuellen Staat Boolean vertritt. Zum Beispiel 0010 (dezimale 2) kann eine Reihe vier Fahnen betrachtet werden, wo die ersten, dritten und vierten Fahnen (0) klar sind und die zweite Fahne (1) gesetzt wird. Die vierte Fahne kann durch das Durchführen eines bitwise ODER zwischen diesem Wert und wenig Muster gesetzt werden, das 1 nur im vierten Bit enthält:

0010 (dezimale 2)

ODER 1000 (Dezimalzahl 8)

= 1010 (dezimale 10)

Diese Technik ist eine effiziente Weise, mehrere Werte von Boolean mit dem Minimum des Gedächtnisses zu versorgen.

XOR

Ein bitwise XOR nimmt Zwei-Bit-Muster der gleichen Länge und führt die logische exklusive ODER-Verknüpfung auf jedem Paar von entsprechenden Bit durch. Das Ergebnis in jeder Position ist 1, wenn nur das erste Bit 1 ist oder nur das zweite Bit 1 ist, aber 0 sein wird, wenn beide 0 sind oder beide 1 sind. Darin führen wir den Vergleich von zwei Bit durch, 1 seiend, wenn die zwei Bit, und 0 verschieden sind, wenn sie dasselbe sind. Zum Beispiel:

0101 (dezimale 5)

XOR 0011 (dezimale 3)

= 0110 (dezimale 6)

Der bitwise XOR kann verwendet werden, um ausgewählte Bit in einem Register (auch genannt Knebelknopf oder Flip) umzukehren. In Anbetracht des Bit-Musters 0010 (dezimale 2) können die zweiten und vierten Bit toggled durch einen bitwise XOR mit wenig Muster sein, das 1 in den zweiten und vierten Positionen enthält:

0010 (dezimale 2)

XOR 1010 (dezimale 10)

= 1000 (Dezimalzahl 8)

Diese Technik kann verwendet werden, um Bit-Muster zu manipulieren, die Sätze von Staaten von Boolean vertreten.

Zusammenbau-Sprachprogrammierer verwenden manchmal XOR als eine Abkürzung zum Setzen des Werts eines Registers zur Null. Das Durchführen von XOR auf einem Wert gegen sich gibt immer Null nach, und auf vielen Architekturen verlangt diese Operation weniger Uhr-Zyklen und/oder Gedächtnis als das Laden eines Nullwerts und Sparen davon zum Register.

Siehe auch

• XOR tauschen Algorithmus
• XOR hat Liste verbunden

Bit-Verschiebungen

Die Bit-Verschiebungen werden manchmal als bitwise Operationen betrachtet, weil sie auf der binären Darstellung einer ganzen Zahl statt seines numerischen Werts funktionieren; jedoch funktionieren die Bit-Verschiebungen auf Paaren von entsprechenden Bit nicht, und können deshalb mit dem Bit klug nicht richtig genannt werden. In diesen Operationen werden die Ziffern bewegt, oder, nach links oder Recht ausgewechselt. Register in einem Computerverarbeiter haben eine feste Breite, so werden einige Bit" des Registers an einem Ende "ausgewechselt, während dieselbe Zahl von Bit in" vom anderen Ende "ausgewechselt wird; die Unterschiede zwischen dem Bit bewegen sich Maschinenbediener lügen darin, wie sie die Werte des ausgewechselten - in Bit bestimmen.

Arithmetische Verschiebung

In einer arithmetischen Verschiebung werden die Bit, die aus jedem Ende ausgewechselt werden, verworfen. In einer linken arithmetischen Verschiebung werden Nullen in rechts ausgewechselt; in einer richtigen arithmetischen Verschiebung hat das Zeichen gebissen wird in links ausgewechselt, so das Zeichen des operand bewahrend. Weiter auf, während man Recht auswechseln wird, werden die leeren Räume mit einer Kopie des bedeutendsten Bit (MSB) voll gefüllt. Vorhabend, indem Sie das zweite arithmetische Verschiebungsregister (ASR#2) mit einem MSB=1 auswechseln, füllen Sie sich mit 1.

Dieses Beispiel verwendet ein 8-Bit-Register:

00010111 (dezimale +23) WECHSELN NACH LINKS AUS

= 00101110 (dezimale +46)

10010111 (dezimale 105) RICHTIGE VERSCHIEBUNG

= 11001011 (dezimale 53)

Im ersten Fall wurde die leftmost Ziffer vorbei am Ende des Registers ausgewechselt, und neuer 0 wurde in die niedrigstwertige Position ausgewechselt. Im zweiten Fall wurde niedrigstwertiger 1 (vielleicht in die tragen Fahne) ausgewechselt, und neuer 1 wurde in die leftmost Position kopiert, das Zeichen der Zahl bewahrend. Vielfache Verschiebungen werden manchmal zu einer einzelnen Verschiebung durch eine Zahl von Ziffern verkürzt. Zum Beispiel:

00010111 (dezimale +23) VERLASSEN VERSCHIEBUNG DURCH ZWEI

= 01011100 (dezimale +92)

Eine linke arithmetische Verschiebung durch n ist zum Multiplizieren mit 2 gleichwertig (vorausgesetzt dass der Wert nicht überfließt), während eine richtige arithmetische Verschiebung durch n eines Ergänzungswerts eines two zum Teilen durch 2 und das Runden zur negativen Unendlichkeit gleichwertig ist. Wenn die Binärzahl als die Ergänzung von behandelt wird, dann läuft dieselbe Operation der richtigen Verschiebung auf Abteilung durch 2 und das Runden zur Null hinaus.

Logische Verschiebung

In einer logischen Verschiebung werden Nullen ausgewechselt in, die verworfenen Bit zu ersetzen. Deshalb sind die logischen und arithmetischen nach links Verschiebungen genau dasselbe.

Jedoch, da die logischen Einsätze der richtigen Verschiebung 0 Bit ins bedeutendste Bit schätzen, anstatt das Zeichen-Bit zu kopieren, ist es für nicht unterzeichnete Binärzahlen ideal, während die arithmetische richtige Verschiebung für die Ergänzungsbinärzahlen von unterzeichnetem two ideal ist.

Rotieren Sie nicht tragen

Eine andere Form der Verschiebung ist die kreisförmige Verschiebung oder beißt Folge. In dieser Operation werden die Bit "rotieren gelassen", als ob die verlassenen und richtige Enden des Registers angeschlossen wurden. Der Wert, der in rechts während einer nach links Verschiebung ausgewechselt wird, ist beliebiger Wert wurde links, und umgekehrt ausgewechselt. Diese Operation ist nützlich, wenn es notwendig ist, alle vorhandenen Bit zu behalten, und oft in der Digitalgeheimschrift verwendet wird.

Rotieren Sie durch tragen

Rotieren Sie durch tragen ist dem Rotieren ähnlich nicht tragen Operation, aber die zwei Enden des Registers werden durch die tragen Fahne getrennt. Das Bit, das darin ausgewechselt wird (auf jedem Ende) ist der alte Wert der tragen Fahne, und das Bit, das ausgewechselt wird (auf dem anderen Ende) wird der neue Wert der tragen Fahne.

Eine Single rotiert durch tragen kann eine logische oder arithmetische Verschiebung einer Position durch die Aufstellung der tragen Fahne im Voraus vortäuschen. Zum Beispiel, wenn die tragen Fahne 0 enthält, dann eine logische richtige Verschiebung ist, und wenn die tragen Fahne eine Kopie des Zeichens enthält, hat gebissen, ist dann eine arithmetische richtige Verschiebung. Deshalb haben einige Mikrokontrolleure wie FILME gerade rotieren und rotieren durch tragen, und sorgen sich mit arithmetischen oder logischen Verschiebeanweisungen nicht.

Rotieren Sie durch tragen ist besonders nützlich, wenn man Verschiebungen auf Zahlen durchführt, die größer sind als die heimische Wortgröße des Verarbeiters, weil, wenn eine Vielzahl in zwei Registern versorgt wird, das Bit, das vom Ende des ersten Registers ausgewechselt wird, am anderen Ende des zweiten eingehen muss. Mit rotate-carry, in dem Bit in der tragen Fahne während der ersten Verschiebung "gespart", bereit wird, sich während der zweiten Verschiebung ohne jede Extravorbereitung zu bewegen.

Verschiebungen in C, C ++, C#

Auf C-inspired Sprachen bewegen sich der verlassene und das Recht Maschinenbediener sind ""und"" beziehungsweise. Die Zahl von Plätzen sich zu bewegen wird als das zweite Argument für die Verschiebungsmaschinenbediener gegeben. Zum Beispiel,

teilt x das Ergebnis zu, y nach links durch zwei Bit auszuwechseln.

In C und C ++, Berechnung mit dem linken operand als ein nicht unterzeichneter Gebrauch der ganzen Zahl logische Verschiebungen. In C# ist die richtige Verschiebung eine arithmetische Verschiebung, wenn der erste operand eine interne Nummer oder lange ist. Wenn der erste operand des Typs uint oder ulong ist, ist die richtige Verschiebung eine logische Verschiebung. In C, den Ergebnissen mit dem linken operand als eine unterzeichnete ganze Zahl sind:

Im allgemeinen Fall:

• für "": Y×2 (unbestimmt, wenn eine Überschwemmung vorkommt);
• für "": Durchführungsdefiniert (meistenteils das Ergebnis der arithmetischen Verschiebung: Y/2).

Es gibt auch mit dem Bearbeiter spezifischen intrinsics das Einführen kreisförmiger Verschiebungen, wie _rotl8, _rotl16, _rotr8, _rotr16 in Microsoft Visual C ++.

Verschiebungen in Java

In Java werden alle Typen der ganzen Zahl, und "" unterzeichnet, und "" Maschinenbediener führen arithmetische Verschiebungen durch. Java fügt den Maschinenbediener "" hinzu, um logische richtige Verschiebungen durchzuführen, aber weil die logischen und arithmetischen Operationen der nach links Verschiebung identisch sind, gibt es nicht "" Maschinenbediener in Java. Diese allgemeinen Regeln werden auf mehrere Weisen durch die Verzug-Typ-Promotionen betroffen; zum Beispiel, weil der Acht-Bit-Typ in shift-expressions gefördert wird, führt der Ausdruck "" effektiv eine arithmetische Verschiebung des Byte-Werts statt einer logischen Verschiebung durch. Solche Effekten können durch den vernünftigen Gebrauch von Würfen oder bitmasks gelindert werden; zum Beispiel, "" läuft effektiv auf eine logische Verschiebung hinaus.

Verschiebungen in Pascal

In Pascal, sowie in allen seinen Dialekten (wie Object Pascal und Standard Pascal) bewegen sich der verlassene und das Recht Maschinenbediener sind ""und"" beziehungsweise. Die Zahl von Plätzen sich zu bewegen wird als das zweite Argument gegeben. Zum Beispiel teilt der folgende x das Ergebnis zu, y nach links durch zwei Bit auszuwechseln:

Anwendungen

Operationen von Bitwise sind für viel auf niedriger Stufe Programmierung, wie das Schreiben von Gerät-Fahrern, auf niedriger Stufe Grafik, Kommunikationsprotokoll-Paket-Zusammenbau und Entzifferung notwendig.

Obwohl Maschinen häufig effiziente eingebaute Instruktionen haben, um arithmetische und logische Operationen tatsächlich durchzuführen, können alle diese Operationen durch das Kombinieren der bitwise Maschinenbediener und Nullprüfung auf verschiedene Weisen durchgeführt werden.

Zum Beispiel ist hier ein Pseudocodebeispiel, das sich zeigt, wie man zwei willkürliche ganze Zahlen und (größer multipliziert als) das Verwenden nur bitshifts und die Hinzufügung:

c: = 0

während b  0

wenn (b und 1)  0

c: = c + ein

verlassene Verschiebung durch 1

richtige Verschiebung b durch 1

geben Sie c zurück

</Code>

Diese Durchführung der alten ägyptischen Multiplikation, wie die meisten Multiplikationsalgorithmen, ist mit bitshifts verbunden. Der Reihe nach kann sogar Hinzufügung mit gerade bitshifts und Nullprüfung geschrieben werden:

c: = b und ein

während ein  0

c: = b und ein

b: = b xor ein

verlassene Verschiebung c durch 1

a: = c

geben Sie b zurück

</Code>

Siehe auch

• Bit-Manipulation
• Operationen von Bitwise in C
• Finden Sie den ersten Satz
• Bitboard
• Algebra von Boolean (Logik)
• Doppelt plätschern
• Logiktor
• Logischer Maschinenbediener
• Karnaugh stellen kartografisch dar

Links

• Bitwise Online-Rechenmaschine unterstützt Bitwise UND, ODER und XOR
• Abteilung mit bitshifts
• "Bitwise Operationen Mod N" durch Enrique Zeleny, Wolfram-Demonstrationsprojekt.
• "Anschläge von Zusammensetzungen von Bitwise Operationen" durch Enrique Zeleny, das Wolfram-Demonstrationsprojekt.