„Bitweiser Operator“ – Versionsunterschied
[gesichtete Version] | [gesichtete Version] |
Typo |
InternetArchiveBot hat 1 Archivlink(s) ergänzt und 0 Link(s) als defekt/tot markiert.) #IABot (v2.0.9.5 |
||
(35 dazwischenliegende Versionen von 17 Benutzern werden nicht angezeigt) | |||
Zeile 1: | Zeile 1: | ||
In der [[Informatik]] ist ein '''bitweiser Operator''' ein [[Operator (Mathematik)|Operator]], der auf ein oder zwei |
In der [[Informatik]] ist ein '''bitweiser Operator''' ein [[Operator (Mathematik)|Operator]], der auf ein oder zwei [[Bitkette]]n, [[Bitfeld]]ern, Bitfolgen oder Bitvektoren auf der Ebene der einzelnen [[Bit]]s angewendet wird. Insbesondere in den Programmiersprachen der [[C (Programmiersprache)|C]]-Familie können [[Dualsystem|Binärzahlen]] ohne weitere [[Syntax#Syntax formaler Sprachen|syntaktische]] Kennzeichnung als Bitfolgen aufgefasst werden. |
||
Die zugrundeliegenden Operationen auf den einzelnen Bits sind [[Logikgatter|schaltungstechnisch]] die allereinfachsten, und alle höheren Operationen lassen sich auf sie zurückführen. Die ''bitweisen'' Operationen werden wegen ihrer geringeren Bedeutung für die Geschwindigkeit eines Computersystems jedoch meist weniger durch Optimierung bevorzugt als die komplexeren arithmetischen Operationen wie Addition und Subtraktion. |
|||
== Bitweise Operatoren == |
== Bitweise Operatoren == |
||
Die Sprechweise ''bitweise'' deutet darauf hin, dass die mehrgliedrigen Eingabeoperanden [[Vektor#Rechenoperationen|komponentenweise]] verarbeitet werden. (Sie können natürlich auch eingliedrig sein.) Man kann davon ausgehen, dass bei zweistelligen Operationen verschieden lange Operanden vom [[Kompiler]] als Fehler angesehen werden. |
|||
In vielen Programmiersprachen der [[C (Programmiersprache)|C]]-Familie wird syntaktisch und semantisch zwischen bitweise (= mehrgliedrig und komponentenweise) und logisch (= boolesch = eine einzige Komponente) unterschieden. Letztere werden wegen der naheliegenden Verwechslungsgefahr in diesem Artikel zusätzlich aufgeführt. |
|||
=== NICHT === |
=== NICHT === |
||
Das ''bitweise NICHT'' oder ''Komplement'' ist eine [[einstellige Verknüpfung]], die eine logische [[Negation]] (Inversion) jedes Bits durchführt. Wird die Bitfolge als Binärzahl aufgefasst, dann ist dies die Bildung des [[Einerkomplement]]s. Jede <code>0</code> wird durch eine <code>1</code> ausgetauscht und umgekehrt. Beispiel: |
|||
NICHT 0111 |
NICHT 0111 |
||
= 1000 |
= 1000 |
||
In vielen Programmiersprachen der [[C (Programmiersprache)|C]]-Familie wird das bitweise NICHT als <code>~</code> ([[Tilde]]) dargestellt |
In vielen Programmiersprachen der [[C (Programmiersprache)|C]]-Familie wird das bitweise NICHT als <code>~</code> ([[Tilde]]) dargestellt. |
||
Im Gegensatz dazu wird beim [[Logischer Operator|logischen Operator]] <code>!</code> (Ausrufezeichen) für ''logisches NICHT'' der gesamte Wert als Boolescher Ausdruck <code>true ≠ 0</code> oder <code>false = 0</code> interpretiert. Das ''logische NICHT'' ist keine bitweise Operation. |
|||
NICHT ( |
NICHT (bitweise): ~0 = 1 |
||
~1<sub>dez</sub> = 0<sub>dez</sub> |
|||
NICHT (Bitweise): ~1d = 0d; ~5d = ~0101b = 1010b = 10d |
|||
~5<sub>dez</sub> = ~0101<sub>bin</sub> = 1010<sub>bin</sub> = 10<sub>dez</sub> |
|||
NICHT (logisch): !false = true |
|||
!true = false |
|||
!0 = true |
|||
!1<sub>dez</sub> = false |
|||
!5<sub>dez</sub> = false |
|||
=== |
=== UND === |
||
[[Datei:0...15 AND.svg|mini|Bitweises [[Konjunktion (Logik)|UND]] von 4 [[Bit]]]] |
|||
Ein ''bitweises ODER'' wird auf zwei Bitfolgen gleicher Länge angewendet und gibt eine Bitfolge derselben Länge zurück, indem es jeweils Bits an der gleichen Stelle (jeweils das erste Bit, jeweils das zweite Bit usw.) mit einem logischen ODER (logische [[Disjunktion]]) verknüpft. Bei jedem Paar ist das Ergebnisbit <code>1</code>, falls das Bit der ersten Bitfolge <code>1</code> ist ''ODER'' das Bit der zweiten Bitfolge <code>1</code> ist, ansonsten ist das Ergebnisbit <code>0</code>. Beispiel: |
|||
0101 |
|||
ODER 0011 |
|||
= 0111 |
|||
In den mit C verwandten Programmiersprachen wird das bitweise ODER durch <code>|</code> ([[senkrechter Strich]]) dargestellt. Dieser Operator darf nicht mit seinem booleschen Gegenstück verwechselt werden, das seine Operanden als boolesche Werte interpretiert und als <code>||</code> (zwei senkrechte Striche) dargestellt wird. |
|||
Das bitweise ODER wird verwendet, wenn mehrere Bits als [[Flag (Informatik)|Flags]] verwendet werden; die Bits einer einzelnen Binärzahl können jeweils eine eigene boolesche Variable darstellen. Wendet man das bitweise ODER auf einen solchen Binärwert und eine „Maske“ an, die an bestimmten Stellen eine <code>1</code> enthält, so erhält man eine neue Bitfolge, in der diese Bits zusätzlich zu den ursprünglich vorhandenen gesetzt sind. Beispiel: |
|||
0010 |
|||
kann als Liste von vier Flags angesehen werden. Das erste, zweite und vierte Flag sind nicht gesetzt (<code>0</code>), das dritte Flag ist gesetzt (<code>1</code>). Das erste Flag kann gesetzt werden, indem man diese Bitfolge mit einer Bitfolge verknüpft, die nur an der ersten Stelle eine <code>1</code> hat: |
|||
Das ''bitweise UND'' wird auf zwei Bitfolgen gleicher Länge angewendet und gibt eine Bitfolge derselben Länge zurück, indem es jeweils Bits an der gleichen Stelle (jeweils das erste Bit, jeweils das zweite Bit usw.) mit einem logischen UND ([[Konjunktion (Logik)|logische Konjunktion]]) verknüpft. Bei jedem Paar ist das Ergebnisbit <code>1</code>, falls beide Bits <code>1</code> sind, ansonsten <code>0</code>. Beispiel: |
|||
0010 |
|||
OR 1000 |
|||
= 1010 |
|||
Diese Technik wird eingesetzt, um Speicherplatz zu sparen, wenn Programme sehr viele Boolesche Werte verwalten müssen. |
|||
=== XOR === |
|||
Ein ''bitweises exklusives ODER'' wird auf zwei Bitfolgen der gleichen Länge angewendet und führt die logische [[XOR]]-Operation auf jedem Paar korrespondierender Bits durch. Das Ergebnisbit ist <code>1</code>, falls die zwei Bits unterschiedlich sind, und <code>0</code>, falls sie gleich sind. Beispiel: |
|||
0101 |
|||
XOR 0011 |
|||
= 0110 |
|||
In den mit C verwandten Programmiersprachen wird das bitweise XOR als <code>^</code> ([[Circumflex]]) dargestellt. |
|||
In der [[Assemblersprache]] wird das bitweise XOR gelegentlich eingesetzt, um den Wert eines [[Register (Computer)|Prozessorregisters]] auf <code>0</code> zu setzen. Wendet man XOR auf zwei identische Operanden an, so erhält man immer <code>0</code>. In vielen Architekturen benötigt diese Operation weniger Rechenzeit, als man für das Laden einer <code>0</code> und das Speichern im Register benötigt. |
|||
Das bitweise XOR kann auch verwendet werden, um Flags in Bitfolgen umzuschalten. Beispiel: |
|||
0010 |
|||
Das erste und das dritte Bit können simultan umgeschaltet werden, indem man diese Bitfolge mit XOR mit einer Maske verknüpft, welche die Bits 1 und 3 gesetzt hat: |
|||
0010 |
|||
XOR 1010 |
|||
= 1000 |
|||
Diese Technik kann eingesetzt werden, um Bitfolgen zu manipulieren, die mehrere boolesche Variablen repräsentieren. |
|||
=== UND === |
|||
Ein ''bitweises UND'' wird auf zwei Bitfolgen gleicher Länge angewendet und führt die logische UND-Verknüpfung ([[Konjunktion (Logik)|logische Konjunktion]]) auf jedem Paar korrespondierender Bits durch. Das Ergebnisbit ist <code>1</code>, falls beide Bits <code>1</code> sind, ansonsten <code>0</code>. Beispiel: |
|||
0101 |
0101 |
||
Zeile 64: | Zeile 36: | ||
= 0001 |
= 0001 |
||
In den mit C verwandten Programmiersprachen wird das bitweise UND durch <code>&</code> ([[Et-Zeichen|kaufmännisches Und]], engl. ''ampersand'') dargestellt. |
In den mit C verwandten Programmiersprachen wird das bitweise UND durch <code>&</code> ([[Et-Zeichen|kaufmännisches Und]], engl. ''ampersand'') dargestellt. Das boolesche Gegenstück dazu, das ''logische UND'', interpretiert jeden seiner zwei Operanden als einen booleschen Wert und wird als <code>&&</code> (zwei kaufmännische Und) dargestellt. |
||
Das bitweise UND kann verwendet werden, um eine Bitfolge zu ''maskieren''. Dadurch können Teile eines [[Bitstring]]s isoliert werden, und man kann ermitteln, ob ein bestimmtes Bit gesetzt ist oder nicht. Beispiel: |
Das bitweise UND kann verwendet werden, um eine Bitfolge zu ''maskieren''. Dadurch können Teile eines [[Bitstring]]s isoliert werden, und man kann ermitteln, ob ein bestimmtes Bit gesetzt ist oder nicht. Beispiel: |
||
Zeile 78: | Zeile 50: | ||
Da das Ergebnis nicht Null ist, muss das dritte Bit in der ursprünglichen Bitfolge eine <code>1</code> gewesen sein. Diese Anwendung des bitweisen UND wird ''bitweise Maskierung'' genannt, weil Teile, die nicht geändert werden sollen oder für die Berechnung nicht wichtig sind, ausgeblendet werden. |
Da das Ergebnis nicht Null ist, muss das dritte Bit in der ursprünglichen Bitfolge eine <code>1</code> gewesen sein. Diese Anwendung des bitweisen UND wird ''bitweise Maskierung'' genannt, weil Teile, die nicht geändert werden sollen oder für die Berechnung nicht wichtig sind, ausgeblendet werden. |
||
Das bitweise UND kann mit dem bitweisen NICHT kombiniert werden, um Bits zu löschen. |
Das bitweise UND kann mit dem bitweisen NICHT kombiniert werden, um Bits zu löschen. Beispielsweise soll in der Bitfolge |
||
0110 |
0110 |
||
das zweite Bit ''gelöscht'' (d. h. auf <code>0</code> gesetzt) werden, sodass im Ergebnis <code>0010</code> herauskommt. |
|||
Dies geschieht, indem wir eine invertierte Maske (die Null muss dafür an der Stelle der zu ändernden Ziffer gesetzt werden) auf unsere Bitfolge anwenden. Invertieren können wir mit dem NICHT-Operator. |
Dies geschieht, indem wir eine invertierte Maske (die Null muss dafür an der Stelle der zu ändernden Ziffer gesetzt werden) auf unsere Bitfolge anwenden. Invertieren können wir mit dem NICHT-Operator. |
||
Zeile 93: | Zeile 65: | ||
= 0010 |
= 0010 |
||
Weiterhin ist es mit dem bitweisen UND möglich, eine |
Weiterhin ist es mit dem bitweisen UND möglich, eine Binärzahl [[modulo]] 2<sup>''k''</sup> zu rechnen, |
||
indem man sie mit 2<sup>''k''</sup> |
indem man sie mit 2<sup>''k''</sup>−1 UND-verknüpft. Dadurch werden alle Bits ab der {{nowrap|''k''-ten}} Position von rechts auf 0 gesetzt. |
||
gesetzt, was dann genau dem Ergebnis der modulo-Berechnung entspricht. |
|||
Beispiel: 17 mod 8 = 1 entspricht |
Beispiel: 17 mod 8 = 1 entspricht |
||
010001 (17) |
|||
UND |
UND 000111 (7 = 8−1) |
||
= |
= 000001 |
||
=== ODER === |
|||
== Bitweise Verschiebungen == |
|||
[[Datei:0...15 OR.svg|mini|Bitweises [[ODER]] von 4 [[Bit]]]] |
|||
Das ''bitweise ODER'' wird auf zwei Bitfolgen gleicher Länge angewendet und gibt eine Bitfolge derselben Länge zurück, indem es jeweils Bits an der gleichen Stelle mit einem logischen ODER (logische [[Disjunktion]]) verknüpft. Bei jedem Paar ist das Ergebnisbit <code>0</code>, falls beide Bits <code>0</code> sind, ansonsten ist das Ergebnisbit <code>1</code>. Beispiel: |
|||
0101 |
|||
ODER 0011 |
|||
= 0111 |
|||
In den mit C verwandten Programmiersprachen wird das bitweise ODER durch <code>|</code> ([[senkrechter Strich]]) dargestellt. Das boolesche Gegenstück dazu, das ''logische ODER'', das seine Operanden als boolesche Werte interpretiert, wird als <code>||</code> (zwei senkrechte Striche) dargestellt. |
|||
Das bitweise ODER wird verwendet, wenn mehrere Bits als [[Flag (Informatik)|Flags]] verwendet werden; die Bits einer einzelnen Binärzahl können jeweils eine eigene boolesche Variable darstellen. Wendet man das bitweise ODER auf einen solchen Binärwert und eine „Maske“ an, die an bestimmten Stellen eine <code>1</code> enthält, so erhält man eine neue Bitfolge, in der diese Bits zusätzlich zu den ursprünglich vorhandenen gesetzt sind. Beispiel: |
|||
0010 |
|||
kann als Liste von vier Flags angesehen werden. Das erste, zweite und vierte Flag sind nicht gesetzt (<code>0</code>), das dritte Flag ist gesetzt (<code>1</code>). Das erste Flag kann gesetzt werden, indem man diese Bitfolge mit einer Bitfolge verknüpft, die nur an der ersten Stelle eine <code>1</code> hat: |
|||
0010 |
|||
ODER 1000 |
|||
= 1010 |
|||
Diese Technik wird eingesetzt, um Speicherplatz zu sparen, wenn Programme sehr viele Boolesche Werte verwalten müssen. |
|||
=== XOR === |
|||
[[Datei:Z2^4; Cayley table; binary.svg|mini|Bitweises [[Exklusives Oder|exklusives ODER]] von 4 [[Bit]]]] |
|||
Das ''bitweise exklusive ODER'' wird auf zwei Bitfolgen der gleichen Länge angewendet und gibt eine Bitfolge derselben Länge zurück, indem es die logische [[XOR]]-Operation auf jedem Paar korrespondierender Bits durchführt. Das Ergebnisbit ist <code>1</code>, falls die zwei Bits unterschiedlich sind, und <code>0</code>, falls sie gleich sind. Beispiel: |
|||
0101 |
|||
XOR 0011 |
|||
= 0110 |
|||
In den mit C verwandten Programmiersprachen wird das bitweise XOR als <code>^</code> ([[Circumflex]]) dargestellt. Das boolesche Gegenstück dazu, das logische XOR, das seine zwei Operanden jeweils als einen booleschen Wert auffasst, wird als <code>^^</code> dargestellt. |
|||
In der [[Assemblersprache]] wird das bitweise XOR gelegentlich eingesetzt, um den Wert eines [[Register (Computer)|Prozessorregisters]] auf <code>0</code> zu setzen. Wendet man XOR auf zwei identische Operanden an, so erhält man immer <code>0</code>. In vielen Architekturen benötigt diese Operation weniger Rechenzeit, als man für das Laden einer <code>0</code> und das Speichern im Register benötigt. |
|||
Das bitweise XOR kann auch verwendet werden, um Flags in Bitfolgen umzuschalten. |
|||
Dazu fasst man den zweiten Operanden als [[#NICHT|NICHT-„Maske“]] auf den ersten Operanden auf, die diejenigen Stellen logisch invertiert, an denen eine <code>1</code> steht, und die anderen unverändert lässt. Im Beispiel |
|||
0101 |
|||
XOR 00'''11''' („Maske“) |
|||
= 01'''10''' |
|||
wird das dritte und vierte Flag umgeschaltet. |
|||
Diese Technik kann eingesetzt werden, um Bitfolgen zu manipulieren, die mehrere boolesche Variablen repräsentieren. |
|||
== Bitweise Verschiebungen == |
|||
Bei den ''bitweisen Verschiebungen'' (engl. ''{{lang|en|bitwise shift}}'') werden die Bits als einzelne Zeichen an einer bestimmten Bit-Position aufgefasst – und nicht als Paare korrespondierender Bits wie in den oben stehenden Operationen. Dabei bedeutet das Kollektiv der Bits bei der [[#Arithmetische Verschiebung|arithmetischen Verschiebung]] eine Binärzahl oder bei der – etwas elementareren – [[#Logische Verschiebung|logischen Verschiebung]] eine [[Bitkette]] (resp. eine vorzeichenlose (engl. ''{{lang|en|unsigned}}'') Binärzahl). Der Hauptunterschied besteht in der Behandlung des eventuellen Vorzeichenbits. Schaltungstechnisch können bitweise Verschiebungen und Rotationen um eine beliebige Stellenanzahl in Form von [[Barrel-Shifter]]n realisiert werden. |
Bei den ''bitweisen Verschiebungen'' (engl. ''{{lang|en|bitwise shift}}'') werden die Bits als einzelne Zeichen an einer bestimmten Bit-Position aufgefasst – und nicht als Paare korrespondierender Bits wie in den oben stehenden Operationen. Dabei bedeutet das Kollektiv der Bits bei der [[#Arithmetische Verschiebung|arithmetischen Verschiebung]] eine Binärzahl oder bei der – etwas elementareren – [[#Logische Verschiebung|logischen Verschiebung]] eine [[Bitkette]] (resp. eine vorzeichenlose (engl. ''{{lang|en|unsigned}}'') Binärzahl). Der Hauptunterschied besteht in der Behandlung des eventuellen Vorzeichenbits. Schaltungstechnisch können bitweise Verschiebungen und Rotationen um eine beliebige Stellenanzahl in Form von [[Barrel-Shifter]]n realisiert werden. |
||
Bei diesen Operationen werden die Binär-Zeichen um eine angegebene Anzahl von Bitpositionen nach links oder rechts ''verschoben''. Die Richtungsangabe wird dabei unabhängig von der Rechnerarchitektur (und [[Byte-Reihenfolge|Endianness]]) immer in der Standardkonvention des [[Dualsystem]]s verstanden: Links bedeutet Multiplikation und rechts Division mit einer Zweierpotenz. [[Register (Computer)|Register]] der Prozessoren sowie Datentypen der Programmiersprachen beherbergen eine definierte endliche Anzahl von Bits, weshalb die spezifizierte Anzahl an Bits an einem Ende aus dem Register oder Datum „hinausgeschoben“, während die gleiche Anzahl am anderen Ende „hineingeschoben“ („hereingezogen“) wird. |
Bei diesen Operationen werden die Binär-Zeichen um eine angegebene Anzahl von Bitpositionen nach links oder rechts ''verschoben''. Die Richtungsangabe wird dabei unabhängig von der Rechnerarchitektur (und deren [[Byte-Reihenfolge|Endianness]]) immer in der ''(big-endian)'' Standardkonvention des [[Dualsystem]]s verstanden: Links bedeutet Multiplikation und rechts Division mit einer Zweierpotenz. [[Register (Computer)|Register]] der Prozessoren sowie Datentypen der Programmiersprachen beherbergen eine definierte endliche Anzahl von Bits, weshalb die spezifizierte Anzahl an Bits an einem Ende aus dem Register oder Datum „hinausgeschoben“, während die gleiche Anzahl am anderen Ende „hineingeschoben“ („hereingezogen“) wird. |
||
Auf diese Weise induzieren die bitweisen Verschiebungsoperationen eine [[Bitwertigkeit#Adressierung von Bits|Adressierung der Bits]] innerhalb eines Bytes. |
|||
; Beispiel |
; Beispiel |
||
Zeile 115: | Zeile 133: | ||
* „>>“ (in einigen Sprachen „shr“) Verschieben nach rechts, um den jeweils dahinter angegebenen Wert |
* „>>“ (in einigen Sprachen „shr“) Verschieben nach rechts, um den jeweils dahinter angegebenen Wert |
||
In Sprachen wie C wird für Rechtsverschiebungen abhängig vom Datentyp und ggf. [[Vorzeichen (Zahl)|Vorzeichen]] entweder mit Nullen (unsigned oder nicht-negativ) oder mit Einsen (signed und kleiner Null) aufgefüllt. Andere Programmiersprachen (wie z. B. Java) verwenden stattdessen einen eigenen Operator <code>>>></code>, bei dem stets mit Nullen aufgefüllt wird: |
In Sprachen wie C wird für Rechtsverschiebungen abhängig vom Datentyp und ggf. [[Vorzeichen (Zahl)|Vorzeichen]] entweder mit Nullen (unsigned oder nicht-negativ) oder mit Einsen (signed und kleiner als Null) aufgefüllt. Andere Programmiersprachen (wie z. B. Java) verwenden stattdessen einen eigenen Operator <code>>>></code>, bei dem stets mit Nullen aufgefüllt wird: |
||
00111100 << 1 = 01111000 |
|||
00111100 << 2 = 11110000 |
00111100 << 2 = 11110000 (signed erzeugt einen arithmetischen Überlauf) |
||
11111100 << 2 = 11110000 (signed ohne arithmetischen Überlauf) |
|||
01001111 >> 1 = 00100111 |
01001111 >> 1 = 00100111 |
||
11110000 >> 2 = 11111100 (signed) |
11110000 >> 2 = 11111100 (signed) |
||
11110000 >> |
11110000 >> 2 = 00111100 (unsigned) |
||
11110000 >>> 2 = 00111100 (signed und unsigned) |
|||
01001111 >>> 1 = 00100111 (signed und unsigned) |
01001111 >>> 1 = 00100111 (signed und unsigned) |
||
Eine arithmetische Verschiebung um <math>n</math> (Bitpositionen) ist äquivalent zu einer Multiplikation mit <math>2^{n}</math>. |
Eine logische (oder arithmetische) Verschiebung um <math>n</math> (Bitpositionen) nach ''links'' ist äquivalent zu einer Multiplikation mit <math>2^{n}</math>, sofern keine 1-Bits hinaus- (bzw. in die Vorzeichenposition hinein)geschoben werden ([[Ganzzahlüberlauf]]). Eine arithmetische Verschiebung um <math>n</math> (Bitpositionen) nach ''rechts'' ist äquivalent zu einer Division durch <math>2^{n}</math>; hinausgeschobene 1-Bits gehen verloren. |
||
<math>\mathrm{12_{10} = }</math>< |
<math>\mathrm{12_{10} = }</math><span style="font-family:monospace;">00001100 << 2 = 00110000</span><math>\mathrm{ = 48_{10} = 12 \cdot 2^{2} = 12 \cdot 4}</math> |
||
Dieses Verfahren stellt somit eine Alternative zur Multiplikation bzw. Division mit Zweierpotenzen dar. Divisionsergebnisse werden |
Dieses Verfahren stellt somit eine Alternative zur Multiplikation bzw. Division mit Zweierpotenzen dar. Divisionsergebnisse werden abgeschnitten. Ebenfalls ist es möglich, eine ''n''-Bit-Zahl modulo 2<sup>''k''</sup> zu rechnen, indem sie um jeweils ''n–k'' nach links und wieder nach rechts verschiebt. <!-- Das Ergebnis ist dann die Differenz zwischen der Ausgangszahl und dem Ergebnis der Verschiebungen. --> Etwas schneller noch kann man die modulo-Berechnung über das bitweise UND mit 2<sup>''k''</sup>–1 durchführen. |
||
Eine Verschiebung um 0 Bitpositionen ändert den Wert nicht („identische Abbildung“). Ist für <math>m\ge 0,n\ge 0</math> die Verschiebung um <math>m+n</math> Bitpositionen definiert, dann gilt sowohl für (beidesmal) logische wie für (beidesmal) arithmetische Verschiebungen die „Hintereinanderausführung“: |
|||
((xyz) >> m) >> n = (xyz) >> (m+n) (signed und unsigned) |
|||
((xyz) << m) << n = (xyz) << (m+n) (signed und unsigned) |
|||
D. h.: Abgesehen von der Einschränkung über die Maximalzahl der Schiebepositionen, ab der das Verhalten (implementierungsabhängig und) undefiniert sein kann, genügt es, das Verhalten der Schiebeoperationen für eine (einzige) Schiebeposition zu definieren. |
|||
=== Logische Verschiebung === |
|||
{{Hauptartikel|Logische Verschiebung}} |
|||
{| class="float-right" |
|||
| [[Datei:Rotate right logically.svg|mini|Logischer Rechtsshift]] |
|||
| [[Datei:Rotate left logically.svg|mini|Logischer Linksshift]] |
|||
|} |
|||
Bei einer ''logischen Verschiebung'' (engl. ''{{lang|en|logic shift}}'') werden die hinausgeschobenen Bits verworfen und Nullen nachgezogen, unabhängig von Schieberichtung und Vorzeichen. Deshalb sind logische und arithmetische Verschiebung nach links (bis auf die eventuelle Setzung von Flags) identische Operationen. Bei der logischen Verschiebung nach rechts werden jedoch Nullen statt Kopien des Vorzeichenbits eingefügt. Daher wird die logische Verschiebung bei Bitketten oder vorzeichenlosen Binärzahlen eingesetzt, während arithmetische Verschiebungen bei vorzeichenbehafteten Zweierkomplementzahlen verwendet werden. |
|||
<div style="clear:both;"></div> |
|||
=== Arithmetische Verschiebung === |
=== Arithmetische Verschiebung === |
||
Zeile 136: | Zeile 171: | ||
|} |
|} |
||
Im Gegensatz zur logischen Verschiebung hat bei der ''arithmetischen'' (manchmal auch ''algebraischen'') ''Verschiebung'' (engl. ''{{lang|en|arithmetic shift}}'') das höchstwertige Bit die Rolle des Vorzeichens (in der Darstellung als [[Zweierkomplement]]). Der zugrunde liegende Datentyp ist die vorzeichenbehaftete (<code>signed</code>) binäre Ganzzahl, für die der Compiler den arithmetischen Shift generiert. Hinausgeschobene Bits gehen verloren. Bei einer Verschiebung nach rechts werden Kopien des Vorzeichenbits an der Vorzeichenstelle eingeschoben (engl. ''{{lang|en|sign propagation}}''); bei einer Verschiebung nach links werden auf der rechten Seite Nullen nachgezogen. Beispiel (4-Bit-Register): |
|||
<u>1</u>100 RECHTS-SHIFT um 1 |
<u>1</u>100 RECHTS-SHIFT um 1 |
||
Zeile 144: | Zeile 179: | ||
= 1100 |
= 1100 |
||
Bei der Rechtsverschiebung wird das niedrigstwertige (in |
Bei der Rechtsverschiebung wird das niedrigstwertige (das in der konventionellen Binärdarstellung am weitesten „rechts“ stehende, das Einer-) Bit hinausgeschoben und das [[Bitwertigkeit#Bitreihenfolge|höchstwertige Bit]] (MSB), das „Vorzeichenbit“, am hochwertigen („linken“) Ende erneut eingefügt, wodurch das Vorzeichen der Zahl erhalten bleibt. Bei der Linksverschiebung wird eine neue <code>0</code> am niedrigwertigen („rechten“) Ende eingefügt und das höchstwertige Bit aus dem Register hinausgeschoben. Ist das neue Vorzeichenbit verschieden vom zuletzt hinausgeschobenen (wechselt also das Vorzeichen beim letzten Schiebevorgang), dann wird in vielen Rechnerfamilien das [[Übertragsbit|Überlauf- oder Carry-Flag]] gesetzt, andernfalls gelöscht. |
||
Eine arithmetische Verschiebung um <math>n</math> (Bitpositionen) nach links ist äquivalent zu einer Multiplikation mit <math>2^{n}</math> (sofern kein Überlauf auftritt). Eine arithmetische Verschiebung einer vorzeichenbehafteten (signed) Binärzahl ([[Zweierkomplement]]zahl) um <math>n</math> nach rechts entspricht einer ganzzahligen Division durch <math>2^{n}</math> mit Rundung auf die nächstkleinere Zahl – Beispiele: <code>1>>1 == 0</code> und <code>(-1)>>1 == -1</code>. |
Eine arithmetische Verschiebung um <math>n</math> (Bitpositionen) nach links ist äquivalent zu einer Multiplikation mit <math>2^{n}</math> (sofern kein Überlauf auftritt). Eine arithmetische Verschiebung einer vorzeichenbehafteten (<code>signed</code>) Binärzahl ([[Zweierkomplement]]zahl) um <math>n</math> nach rechts entspricht einer ganzzahligen Division durch <math>2^{n}</math> mit Rundung auf die nächstkleinere Zahl – Beispiele: <code>1>>1 == 1>>31 == 0</code> und <code>(-1)>>1 == (-1)>>31 == -1</code>. |
||
<div style="clear:both;"></div> |
<div style="clear:both;"></div> |
||
=== |
=== Zyklische Verschiebung === |
||
==== Zyklische Verschiebung ohne Übertragsbit ==== |
|||
{| class="float-right" |
|||
| [[Datei:Rotate right logically.svg|mini|Logischer Rechtsshift]] |
|||
| [[Datei:Rotate left logically.svg|mini|Logischer Linksshift]] |
|||
|} |
|||
Bei einer ''logischen Verschiebung'' (engl. ''{{lang|en|logic shift}}'') werden die hinausgeschobenen Bits verworfen und Nullen nachgezogen, unabhängig von Schieberichtung und Vorzeichen. Deshalb sind logische und arithmetische Verschiebung nach links (bis auf die eventuelle Setzung von Flags) identische Operationen. Bei der logischen Verschiebung nach rechts werden jedoch Nullen statt Kopien des Vorzeichenbits eingefügt. Daher wird die logische Verschiebung bei Bitketten oder vorzeichenlosen Binärzahlen eingesetzt, während arithmetische Verschiebungen bei vorzeichenbehafteten Zweierkomplementzahlen verwendet werden. |
|||
<div style="clear:both;"></div> |
|||
=== Zyklische Verschiebung ohne Übertragsbit === |
|||
{| class="float-right" |
{| class="float-right" |
||
| [[Datei:Rotate right.svg|mini|Zyklischer Rechtsshift]] |
| [[Datei:Rotate right.svg|mini|Zyklischer Rechtsshift]] |
||
Zeile 165: | Zeile 191: | ||
|} |
|} |
||
Eine andere Form der bitweisen Verschiebung ist die ''zyklische Verschiebung'' (engl. ''{{lang|en|circular shift}}'') oder ''bitweise Rotation''. Bei dieser Operation „rotieren“ die Bits, als ob das linke und das rechte Ende verbunden wären. Das Bit, das hineingeschoben wird, hat denselben Wert wie das Bit, das aus dem Register hinausgeschoben wird. Diese Operation erhält alle existierenden Bits und wird in einigen Verfahren der digitalen [[Kryptographie]] eingesetzt, beispielsweise beim [[Advanced Encryption Standard#ShiftRows|AES-Verfahren]], von und nach seinen Entwicklern auch „Rijndael“ genannt. In elementarer Form, jedoch nicht auf Bitebene sondern auf der Basis eines [[Alphabet (Kryptologie)|Alphabets]], wird sie in der [[Verschiebechiffre]] angewendet. |
Eine andere Form der bitweisen Verschiebung ist die ''zyklische Verschiebung'' (engl. ''{{lang|en|circular shift}}'') oder ''bitweise Rotation''. Bei dieser Operation „rotieren“ die Bits, als ob das linke und das rechte Ende verbunden wären. Das Bit, das hineingeschoben wird, hat denselben Wert wie das Bit, das aus dem Register hinausgeschoben wird. Diese Operation erhält alle existierenden Bits und wird in einigen Verfahren der digitalen [[Kryptographie]] eingesetzt, beispielsweise beim [[Advanced Encryption Standard#ShiftRows|AES-Verfahren]], von und nach seinen Entwicklern auch „Rijndael“ genannt. In elementarer Form, jedoch nicht auf Bitebene, sondern auf der Basis eines [[Alphabet (Kryptologie)|Alphabets]], wird sie in der [[Verschiebechiffre]] angewendet. |
||
<div style="clear:both;"></div> |
<div style="clear:both;"></div> |
||
=== Zyklische Verschiebung mit Übertragsbit === |
==== Zyklische Verschiebung mit Übertragsbit ==== |
||
{| class="float-right" |
{| class="float-right" |
||
|[[Datei:Rotate right through carry.svg|mini|Zyklischer Rechtsshift mit Übertragsbit C (Carry)]] |
|[[Datei:Rotate right through carry.svg|mini|Zyklischer Rechtsshift mit Übertragsbit C (Carry)]] |
||
Zeile 191: | Zeile 217: | ||
weist der Variable <code>x</code> das Ergebnis der bitweisen Verschiebung von <code>y</code> um zwei Stellen nach links zu. Dies führt zum selben Ergebnis wie <code>x = y * 4</code>. |
weist der Variable <code>x</code> das Ergebnis der bitweisen Verschiebung von <code>y</code> um zwei Stellen nach links zu. Dies führt zum selben Ergebnis wie <code>x = y * 4</code>. |
||
In C und C++ verwenden Berechnungen mit vorzeichenlosen Werten logische Verschiebungen; Berechnungen mit vorzeichenbehafteten Werten |
In C und C++ verwenden Berechnungen mit vorzeichenlosen Werten logische Verschiebungen; Berechnungen mit vorzeichenbehafteten Werten verhalten sich abhängig von der Implementierung (engl. ''{{lang|en|implementation-defined behavior}}''), sofern der rechte Operand negativ ist, durch einen Linksshift sich das Vorzeichen ändert oder ein negativer Wert einem Rechtsshift unterzogen wird.<ref>{{Webarchiv|url=http://std.dkuug.dk/JTC1/SC22/WG14/www/docs/n843.htm |wayback=20220803145528 |text=ISO/IEC-Standard „C programming language“ |archiv-bot=2024-07-29 15:21:26 InternetArchiveBot }}, Abschnitt 6.5.7#5 (englisch)</ref> |
||
Ebenso ist das Ergebnis laut C- und C++-Sprachnorm ''undefiniert'', wenn die Anzahl der Bitverschiebungen größer oder gleich der Bitbreite der Rechenarchitektur ist.<ref>A7.8 Shift Operators, Appendix A. Reference Manual, The C Programming Language</ref> Wird beispielsweise auf einer 32-Bit-Architektur von Intel-Prozessoren gearbeitet (IA32), so bewirkt eine Verschiebung um 32 Stellen oft gar keine Veränderung des Ergebnisses, d. h. für <code>x = y << 32</code> ergibt sich <code>x == y</code>. Der Grund liegt in der Art und Weise, wie die Compiler die Schiebeoperation in Maschinencode umsetzen. Die meisten Prozessoren haben direkte Befehle zum Schieben von Bits, wobei die Anzahl der Verschiebungen nur in begrenzter Breite im Maschinenbefehl codiert wird. Für IA32 sind z. B. 5 Bitstellen vorgesehen, um die Zahl der Verschiebungen abzulegen.<ref>SAL,SAR,SHL,SHR – Shift, Chapter 4. Instruction Set Reference, IA-32 Intel Architecture Software Developer’s Manual</ref> Daher können nur Verschiebungen im Bereich 0 bis 31 korrekt ausgeführt werden. Entsprechende Beschränkungen können für andere Architekturen und Datentypen ebenso vorhanden sein. |
Ebenso ist das Ergebnis laut C- und C++-Sprachnorm ''undefiniert'', wenn die Anzahl der Bitverschiebungen größer oder gleich der Bitbreite der Rechenarchitektur ist.<ref>A7.8 Shift Operators, Appendix A. Reference Manual, The C Programming Language</ref> Wird beispielsweise auf einer 32-Bit-Architektur von Intel-Prozessoren gearbeitet (IA32), so bewirkt eine Verschiebung um 32 Stellen oft gar keine Veränderung des Ergebnisses, d. h. für <code>x = y << 32</code> ergibt sich <code>x == y</code>. Der Grund liegt in der Art und Weise, wie die Compiler die Schiebeoperation in Maschinencode umsetzen. Die meisten Prozessoren haben direkte Befehle zum Schieben von Bits, wobei die Anzahl der Verschiebungen nur in begrenzter Breite im Maschinenbefehl codiert wird. Für IA32 sind z. B. 5 Bitstellen vorgesehen, um die Zahl der Verschiebungen abzulegen.<ref>SAL,SAR,SHL,SHR – Shift, Chapter 4. Instruction Set Reference, IA-32 Intel Architecture Software Developer’s Manual</ref> Daher können nur Verschiebungen im Bereich 0 bis 31 korrekt ausgeführt werden. Entsprechende Beschränkungen können für andere Architekturen und Datentypen ebenso vorhanden sein. |
||
Zeile 214: | Zeile 240: | ||
Siehe auch: [[Dualsystem#Schriftliche Multiplikation|Schriftliche Multiplikation im Binärsystem]] |
Siehe auch: [[Dualsystem#Schriftliche Multiplikation|Schriftliche Multiplikation im Binärsystem]] |
||
Eine sehr interessante Anwendung des [[#XOR|bitweisen XOR]] ist die Gewinnstrategie des [[Nim-Spiel]]s, bei der die Anzahlen sowohl als Binärzahlen wie als Bitketten zu behandeln sind. |
|||
== Siehe auch == |
== Siehe auch == |
Aktuelle Version vom 29. Juli 2024, 17:21 Uhr
In der Informatik ist ein bitweiser Operator ein Operator, der auf ein oder zwei Bitketten, Bitfeldern, Bitfolgen oder Bitvektoren auf der Ebene der einzelnen Bits angewendet wird. Insbesondere in den Programmiersprachen der C-Familie können Binärzahlen ohne weitere syntaktische Kennzeichnung als Bitfolgen aufgefasst werden.
Die zugrundeliegenden Operationen auf den einzelnen Bits sind schaltungstechnisch die allereinfachsten, und alle höheren Operationen lassen sich auf sie zurückführen. Die bitweisen Operationen werden wegen ihrer geringeren Bedeutung für die Geschwindigkeit eines Computersystems jedoch meist weniger durch Optimierung bevorzugt als die komplexeren arithmetischen Operationen wie Addition und Subtraktion.
Bitweise Operatoren
[Bearbeiten | Quelltext bearbeiten]Die Sprechweise bitweise deutet darauf hin, dass die mehrgliedrigen Eingabeoperanden komponentenweise verarbeitet werden. (Sie können natürlich auch eingliedrig sein.) Man kann davon ausgehen, dass bei zweistelligen Operationen verschieden lange Operanden vom Kompiler als Fehler angesehen werden.
In vielen Programmiersprachen der C-Familie wird syntaktisch und semantisch zwischen bitweise (= mehrgliedrig und komponentenweise) und logisch (= boolesch = eine einzige Komponente) unterschieden. Letztere werden wegen der naheliegenden Verwechslungsgefahr in diesem Artikel zusätzlich aufgeführt.
NICHT
[Bearbeiten | Quelltext bearbeiten]Das bitweise NICHT oder Komplement ist eine einstellige Verknüpfung, die eine logische Negation (Inversion) jedes Bits durchführt. Wird die Bitfolge als Binärzahl aufgefasst, dann ist dies die Bildung des Einerkomplements. Jede 0
wird durch eine 1
ausgetauscht und umgekehrt. Beispiel:
NICHT 0111 = 1000
In vielen Programmiersprachen der C-Familie wird das bitweise NICHT als ~
(Tilde) dargestellt.
Im Gegensatz dazu wird beim logischen Operator !
(Ausrufezeichen) für logisches NICHT der gesamte Wert als Boolescher Ausdruck true ≠ 0
oder false = 0
interpretiert. Das logische NICHT ist keine bitweise Operation.
NICHT (bitweise): ~0 = 1 ~1dez = 0dez ~5dez = ~0101bin = 1010bin = 10dez NICHT (logisch): !false = true !true = false !0 = true !1dez = false !5dez = false
UND
[Bearbeiten | Quelltext bearbeiten]Das bitweise UND wird auf zwei Bitfolgen gleicher Länge angewendet und gibt eine Bitfolge derselben Länge zurück, indem es jeweils Bits an der gleichen Stelle (jeweils das erste Bit, jeweils das zweite Bit usw.) mit einem logischen UND (logische Konjunktion) verknüpft. Bei jedem Paar ist das Ergebnisbit 1
, falls beide Bits 1
sind, ansonsten 0
. Beispiel:
0101 UND 0011 = 0001
In den mit C verwandten Programmiersprachen wird das bitweise UND durch &
(kaufmännisches Und, engl. ampersand) dargestellt. Das boolesche Gegenstück dazu, das logische UND, interpretiert jeden seiner zwei Operanden als einen booleschen Wert und wird als &&
(zwei kaufmännische Und) dargestellt.
Das bitweise UND kann verwendet werden, um eine Bitfolge zu maskieren. Dadurch können Teile eines Bitstrings isoliert werden, und man kann ermitteln, ob ein bestimmtes Bit gesetzt ist oder nicht. Beispiel:
0011
Um herauszufinden, ob das dritte Bit gesetzt ist oder nicht, wird darauf ein bitweises UND mit einer Maske angewendet, die an der dritten Position eine 1
enthält:
0011 UND 0010 = 0010
Da das Ergebnis nicht Null ist, muss das dritte Bit in der ursprünglichen Bitfolge eine 1
gewesen sein. Diese Anwendung des bitweisen UND wird bitweise Maskierung genannt, weil Teile, die nicht geändert werden sollen oder für die Berechnung nicht wichtig sind, ausgeblendet werden.
Das bitweise UND kann mit dem bitweisen NICHT kombiniert werden, um Bits zu löschen. Beispielsweise soll in der Bitfolge
0110
das zweite Bit gelöscht (d. h. auf 0
gesetzt) werden, sodass im Ergebnis 0010
herauskommt.
Dies geschieht, indem wir eine invertierte Maske (die Null muss dafür an der Stelle der zu ändernden Ziffer gesetzt werden) auf unsere Bitfolge anwenden. Invertieren können wir mit dem NICHT-Operator.
NICHT 0100 = 1011
Danach wird die Bitfolge und die Maske mittels UND-Operator verknüpft:
0110 UND 1011 = 0010
Weiterhin ist es mit dem bitweisen UND möglich, eine Binärzahl modulo 2k zu rechnen, indem man sie mit 2k−1 UND-verknüpft. Dadurch werden alle Bits ab der k-ten Position von rechts auf 0 gesetzt.
Beispiel: 17 mod 8 = 1 entspricht
010001 (17) UND 000111 (7 = 8−1) = 000001
ODER
[Bearbeiten | Quelltext bearbeiten]Das bitweise ODER wird auf zwei Bitfolgen gleicher Länge angewendet und gibt eine Bitfolge derselben Länge zurück, indem es jeweils Bits an der gleichen Stelle mit einem logischen ODER (logische Disjunktion) verknüpft. Bei jedem Paar ist das Ergebnisbit 0
, falls beide Bits 0
sind, ansonsten ist das Ergebnisbit 1
. Beispiel:
0101 ODER 0011 = 0111
In den mit C verwandten Programmiersprachen wird das bitweise ODER durch |
(senkrechter Strich) dargestellt. Das boolesche Gegenstück dazu, das logische ODER, das seine Operanden als boolesche Werte interpretiert, wird als ||
(zwei senkrechte Striche) dargestellt.
Das bitweise ODER wird verwendet, wenn mehrere Bits als Flags verwendet werden; die Bits einer einzelnen Binärzahl können jeweils eine eigene boolesche Variable darstellen. Wendet man das bitweise ODER auf einen solchen Binärwert und eine „Maske“ an, die an bestimmten Stellen eine 1
enthält, so erhält man eine neue Bitfolge, in der diese Bits zusätzlich zu den ursprünglich vorhandenen gesetzt sind. Beispiel:
0010
kann als Liste von vier Flags angesehen werden. Das erste, zweite und vierte Flag sind nicht gesetzt (0
), das dritte Flag ist gesetzt (1
). Das erste Flag kann gesetzt werden, indem man diese Bitfolge mit einer Bitfolge verknüpft, die nur an der ersten Stelle eine 1
hat:
0010 ODER 1000 = 1010
Diese Technik wird eingesetzt, um Speicherplatz zu sparen, wenn Programme sehr viele Boolesche Werte verwalten müssen.
XOR
[Bearbeiten | Quelltext bearbeiten]Das bitweise exklusive ODER wird auf zwei Bitfolgen der gleichen Länge angewendet und gibt eine Bitfolge derselben Länge zurück, indem es die logische XOR-Operation auf jedem Paar korrespondierender Bits durchführt. Das Ergebnisbit ist 1
, falls die zwei Bits unterschiedlich sind, und 0
, falls sie gleich sind. Beispiel:
0101 XOR 0011 = 0110
In den mit C verwandten Programmiersprachen wird das bitweise XOR als ^
(Circumflex) dargestellt. Das boolesche Gegenstück dazu, das logische XOR, das seine zwei Operanden jeweils als einen booleschen Wert auffasst, wird als ^^
dargestellt.
In der Assemblersprache wird das bitweise XOR gelegentlich eingesetzt, um den Wert eines Prozessorregisters auf 0
zu setzen. Wendet man XOR auf zwei identische Operanden an, so erhält man immer 0
. In vielen Architekturen benötigt diese Operation weniger Rechenzeit, als man für das Laden einer 0
und das Speichern im Register benötigt.
Das bitweise XOR kann auch verwendet werden, um Flags in Bitfolgen umzuschalten.
Dazu fasst man den zweiten Operanden als NICHT-„Maske“ auf den ersten Operanden auf, die diejenigen Stellen logisch invertiert, an denen eine 1
steht, und die anderen unverändert lässt. Im Beispiel
0101 XOR 0011 („Maske“) = 0110
wird das dritte und vierte Flag umgeschaltet. Diese Technik kann eingesetzt werden, um Bitfolgen zu manipulieren, die mehrere boolesche Variablen repräsentieren.
Bitweise Verschiebungen
[Bearbeiten | Quelltext bearbeiten]Bei den bitweisen Verschiebungen (engl. bitwise shift) werden die Bits als einzelne Zeichen an einer bestimmten Bit-Position aufgefasst – und nicht als Paare korrespondierender Bits wie in den oben stehenden Operationen. Dabei bedeutet das Kollektiv der Bits bei der arithmetischen Verschiebung eine Binärzahl oder bei der – etwas elementareren – logischen Verschiebung eine Bitkette (resp. eine vorzeichenlose (engl. unsigned) Binärzahl). Der Hauptunterschied besteht in der Behandlung des eventuellen Vorzeichenbits. Schaltungstechnisch können bitweise Verschiebungen und Rotationen um eine beliebige Stellenanzahl in Form von Barrel-Shiftern realisiert werden.
Bei diesen Operationen werden die Binär-Zeichen um eine angegebene Anzahl von Bitpositionen nach links oder rechts verschoben. Die Richtungsangabe wird dabei unabhängig von der Rechnerarchitektur (und deren Endianness) immer in der (big-endian) Standardkonvention des Dualsystems verstanden: Links bedeutet Multiplikation und rechts Division mit einer Zweierpotenz. Register der Prozessoren sowie Datentypen der Programmiersprachen beherbergen eine definierte endliche Anzahl von Bits, weshalb die spezifizierte Anzahl an Bits an einem Ende aus dem Register oder Datum „hinausgeschoben“, während die gleiche Anzahl am anderen Ende „hineingeschoben“ („hereingezogen“) wird.
Auf diese Weise induzieren die bitweisen Verschiebungsoperationen eine Adressierung der Bits innerhalb eines Bytes.
- Beispiel
Symbolik:
- „<<“ (in einigen Sprachen „shl“) Verschieben nach links, um den jeweils dahinter angegebenen Wert
- „>>“ (in einigen Sprachen „shr“) Verschieben nach rechts, um den jeweils dahinter angegebenen Wert
In Sprachen wie C wird für Rechtsverschiebungen abhängig vom Datentyp und ggf. Vorzeichen entweder mit Nullen (unsigned oder nicht-negativ) oder mit Einsen (signed und kleiner als Null) aufgefüllt. Andere Programmiersprachen (wie z. B. Java) verwenden stattdessen einen eigenen Operator >>>
, bei dem stets mit Nullen aufgefüllt wird:
00111100 << 1 = 01111000 00111100 << 2 = 11110000 (signed erzeugt einen arithmetischen Überlauf) 11111100 << 2 = 11110000 (signed ohne arithmetischen Überlauf) 01001111 >> 1 = 00100111 11110000 >> 2 = 11111100 (signed) 11110000 >> 2 = 00111100 (unsigned) 11110000 >>> 2 = 00111100 (signed und unsigned) 01001111 >>> 1 = 00100111 (signed und unsigned)
Eine logische (oder arithmetische) Verschiebung um (Bitpositionen) nach links ist äquivalent zu einer Multiplikation mit , sofern keine 1-Bits hinaus- (bzw. in die Vorzeichenposition hinein)geschoben werden (Ganzzahlüberlauf). Eine arithmetische Verschiebung um (Bitpositionen) nach rechts ist äquivalent zu einer Division durch ; hinausgeschobene 1-Bits gehen verloren.
00001100 << 2 = 00110000
Dieses Verfahren stellt somit eine Alternative zur Multiplikation bzw. Division mit Zweierpotenzen dar. Divisionsergebnisse werden abgeschnitten. Ebenfalls ist es möglich, eine n-Bit-Zahl modulo 2k zu rechnen, indem sie um jeweils n–k nach links und wieder nach rechts verschiebt. Etwas schneller noch kann man die modulo-Berechnung über das bitweise UND mit 2k–1 durchführen.
Eine Verschiebung um 0 Bitpositionen ändert den Wert nicht („identische Abbildung“). Ist für die Verschiebung um Bitpositionen definiert, dann gilt sowohl für (beidesmal) logische wie für (beidesmal) arithmetische Verschiebungen die „Hintereinanderausführung“:
((xyz) >> m) >> n = (xyz) >> (m+n) (signed und unsigned) ((xyz) << m) << n = (xyz) << (m+n) (signed und unsigned)
D. h.: Abgesehen von der Einschränkung über die Maximalzahl der Schiebepositionen, ab der das Verhalten (implementierungsabhängig und) undefiniert sein kann, genügt es, das Verhalten der Schiebeoperationen für eine (einzige) Schiebeposition zu definieren.
Logische Verschiebung
[Bearbeiten | Quelltext bearbeiten]Bei einer logischen Verschiebung (engl. logic shift) werden die hinausgeschobenen Bits verworfen und Nullen nachgezogen, unabhängig von Schieberichtung und Vorzeichen. Deshalb sind logische und arithmetische Verschiebung nach links (bis auf die eventuelle Setzung von Flags) identische Operationen. Bei der logischen Verschiebung nach rechts werden jedoch Nullen statt Kopien des Vorzeichenbits eingefügt. Daher wird die logische Verschiebung bei Bitketten oder vorzeichenlosen Binärzahlen eingesetzt, während arithmetische Verschiebungen bei vorzeichenbehafteten Zweierkomplementzahlen verwendet werden.
Arithmetische Verschiebung
[Bearbeiten | Quelltext bearbeiten]Im Gegensatz zur logischen Verschiebung hat bei der arithmetischen (manchmal auch algebraischen) Verschiebung (engl. arithmetic shift) das höchstwertige Bit die Rolle des Vorzeichens (in der Darstellung als Zweierkomplement). Der zugrunde liegende Datentyp ist die vorzeichenbehaftete (signed
) binäre Ganzzahl, für die der Compiler den arithmetischen Shift generiert. Hinausgeschobene Bits gehen verloren. Bei einer Verschiebung nach rechts werden Kopien des Vorzeichenbits an der Vorzeichenstelle eingeschoben (engl. sign propagation); bei einer Verschiebung nach links werden auf der rechten Seite Nullen nachgezogen. Beispiel (4-Bit-Register):
1100 RECHTS-SHIFT um 1 = 1110
0110 LINKS-SHIFT um 1 = 1100
Bei der Rechtsverschiebung wird das niedrigstwertige (das in der konventionellen Binärdarstellung am weitesten „rechts“ stehende, das Einer-) Bit hinausgeschoben und das höchstwertige Bit (MSB), das „Vorzeichenbit“, am hochwertigen („linken“) Ende erneut eingefügt, wodurch das Vorzeichen der Zahl erhalten bleibt. Bei der Linksverschiebung wird eine neue 0
am niedrigwertigen („rechten“) Ende eingefügt und das höchstwertige Bit aus dem Register hinausgeschoben. Ist das neue Vorzeichenbit verschieden vom zuletzt hinausgeschobenen (wechselt also das Vorzeichen beim letzten Schiebevorgang), dann wird in vielen Rechnerfamilien das Überlauf- oder Carry-Flag gesetzt, andernfalls gelöscht.
Eine arithmetische Verschiebung um (Bitpositionen) nach links ist äquivalent zu einer Multiplikation mit (sofern kein Überlauf auftritt). Eine arithmetische Verschiebung einer vorzeichenbehafteten (signed
) Binärzahl (Zweierkomplementzahl) um nach rechts entspricht einer ganzzahligen Division durch mit Rundung auf die nächstkleinere Zahl – Beispiele: 1>>1 == 1>>31 == 0
und (-1)>>1 == (-1)>>31 == -1
.
Zyklische Verschiebung
[Bearbeiten | Quelltext bearbeiten]Zyklische Verschiebung ohne Übertragsbit
[Bearbeiten | Quelltext bearbeiten]Eine andere Form der bitweisen Verschiebung ist die zyklische Verschiebung (engl. circular shift) oder bitweise Rotation. Bei dieser Operation „rotieren“ die Bits, als ob das linke und das rechte Ende verbunden wären. Das Bit, das hineingeschoben wird, hat denselben Wert wie das Bit, das aus dem Register hinausgeschoben wird. Diese Operation erhält alle existierenden Bits und wird in einigen Verfahren der digitalen Kryptographie eingesetzt, beispielsweise beim AES-Verfahren, von und nach seinen Entwicklern auch „Rijndael“ genannt. In elementarer Form, jedoch nicht auf Bitebene, sondern auf der Basis eines Alphabets, wird sie in der Verschiebechiffre angewendet.
Zyklische Verschiebung mit Übertragsbit
[Bearbeiten | Quelltext bearbeiten]Zyklische Verschiebung mit Übertragsbit (engl. rotate through carry) funktioniert ähnlich wie die zyklische Verschiebung ohne Übertragsbit, jedoch werden die beiden Enden des Registers behandelt, als ob sie durch das Übertragsbit getrennt werden. Das Carry-Bit wird in das Register hineingeschoben, das aus dem Register hinausgeschobene Bit wird zum neuen Übertragsbit.
Eine einzelne zyklische Verschiebung mit Übertragsbit kann eine logische oder arithmetische Verschiebung um eine Stelle simulieren, wenn das Übertragsbit vorher entsprechend gesetzt wird. Enthält das Übertragsbit beispielsweise eine 0
, dann entspricht die Verschiebung nach rechts einer arithmetischen Verschiebung nach rechts. Aus diesem Grund sind bei manchen Mikroprozessoren wie dem PICmicro nur Befehle für die beiden zyklischen Verschiebungsoperationen implementiert, es gibt keine speziellen Befehle für arithmetische oder logische Verschiebungen.
Zyklische Verschiebung mit Übertragsbit ist besonders nützlich, wenn Verschiebungen mit Zahlen durchgeführt werden, die größer als die Wortbreite des Prozessors sind, weil die Zahl dann in zwei Registern gespeichert wird und das aus einem Register hinausgeschobene Bit in das andere Register hineingeschoben werden muss. Bei zyklischer Verschiebung mit Übertragsbit wird dieses Bit bei der ersten Verschiebung im Übertragsbit „gespeichert“ und bei der nächsten Verschiebung weitergegeben, ohne dass zusätzliche Instruktionen notwendig sind.
Verschiebeoperatoren in Programmiersprachen
[Bearbeiten | Quelltext bearbeiten]C und C++
[Bearbeiten | Quelltext bearbeiten]In C, C++ und verwandten Sprachen werden die Verschiebungsoperatoren durch <<
und >>
dargestellt. Die Anzahl der Verschiebungen wird als zweiter Operand übergeben. Beispiel:
x = y << 2;
weist der Variable x
das Ergebnis der bitweisen Verschiebung von y
um zwei Stellen nach links zu. Dies führt zum selben Ergebnis wie x = y * 4
.
In C und C++ verwenden Berechnungen mit vorzeichenlosen Werten logische Verschiebungen; Berechnungen mit vorzeichenbehafteten Werten verhalten sich abhängig von der Implementierung (engl. implementation-defined behavior), sofern der rechte Operand negativ ist, durch einen Linksshift sich das Vorzeichen ändert oder ein negativer Wert einem Rechtsshift unterzogen wird.[1]
Ebenso ist das Ergebnis laut C- und C++-Sprachnorm undefiniert, wenn die Anzahl der Bitverschiebungen größer oder gleich der Bitbreite der Rechenarchitektur ist.[2] Wird beispielsweise auf einer 32-Bit-Architektur von Intel-Prozessoren gearbeitet (IA32), so bewirkt eine Verschiebung um 32 Stellen oft gar keine Veränderung des Ergebnisses, d. h. für x = y << 32
ergibt sich x == y
. Der Grund liegt in der Art und Weise, wie die Compiler die Schiebeoperation in Maschinencode umsetzen. Die meisten Prozessoren haben direkte Befehle zum Schieben von Bits, wobei die Anzahl der Verschiebungen nur in begrenzter Breite im Maschinenbefehl codiert wird. Für IA32 sind z. B. 5 Bitstellen vorgesehen, um die Zahl der Verschiebungen abzulegen.[3] Daher können nur Verschiebungen im Bereich 0 bis 31 korrekt ausgeführt werden. Entsprechende Beschränkungen können für andere Architekturen und Datentypen ebenso vorhanden sein.
Java
[Bearbeiten | Quelltext bearbeiten]In Java sind alle Ganzzahl-Datentypen vorzeichenbehaftet, und die Operatoren <<
und >>
führen arithmetische Verschiebungen durch. In Java gibt es zusätzlich den Operator >>>
, der eine logische Rechtsverschiebung durchführt. Da logische und arithmetische Linksverschiebungen identisch sind, gibt es keinen <<<
-Operator.
ARM-Assembler
[Bearbeiten | Quelltext bearbeiten]In ARM-Assembler werden die Verschiebungsoperatoren durch LSL
(Logical Shift Left), LSR
(Logical Shift Right) und ASR
(Arithmetic Shift Right) dargestellt. Für die zyklischen Verschiebungen gibt es die beiden Befehle ROR
(ROtate Right, ohne Übertragsbit) und RRX
(Rotate Right eXtended, mit Übertragsbit).
Anwendungen
[Bearbeiten | Quelltext bearbeiten]Obwohl Rechner oft effiziente Befehle zur Ausführung von arithmetischen und logischen Operationen eingebaut haben, können alle diese Operationen auch durch Kombinationen von bitweisen Operatoren und Nullvergleichen durchgeführt werden. Folgender Pseudocode zeigt beispielsweise, wie zwei beliebige Ganzzahlen a
und b
nur mithilfe von Verschiebungen und Additionen multipliziert werden können:
c := 0 solange b ≠ 0 falls (b und 1) ≠ 0 c := c + a schiebe a um 1 nach links schiebe b um 1 nach rechts return c
Der Code führt eine schriftliche Multiplikation im Binärsystem aus, allerdings in der unüblichen Reihenfolge von hinten nach vorne (beginnend mit der letzten Ziffer von b
).
Siehe auch: Schriftliche Multiplikation im Binärsystem
Eine sehr interessante Anwendung des bitweisen XOR ist die Gewinnstrategie des Nim-Spiels, bei der die Anzahlen sowohl als Binärzahlen wie als Bitketten zu behandeln sind.
Siehe auch
[Bearbeiten | Quelltext bearbeiten]Weblinks
[Bearbeiten | Quelltext bearbeiten]- Division durch bitweise Verschiebung (englisch)
Einzelnachweise
[Bearbeiten | Quelltext bearbeiten]- ↑ ISO/IEC-Standard „C programming language“ ( des vom 3. August 2022 im Internet Archive) Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis. , Abschnitt 6.5.7#5 (englisch)
- ↑ A7.8 Shift Operators, Appendix A. Reference Manual, The C Programming Language
- ↑ SAL,SAR,SHL,SHR – Shift, Chapter 4. Instruction Set Reference, IA-32 Intel Architecture Software Developer’s Manual