Bitwise-bewerking

De bitverschuivingen worden soms beschouwd als bitwise-bewerkingen, omdat ze een waarde behandelen als een reeks bits in plaats van als een numerieke grootheid. Bij deze bewerkingen worden de cijfers naar links of naar rechts verschoven. Registers in een computerprocessor hebben een vaste breedte, dus sommige bits worden aan de ene kant uit het register “verschoven”, terwijl hetzelfde aantal bits aan de andere kant wordt “verschoven”; de verschillen tussen de bitverschuivingsoperatoren zitten in de manier waarop ze de waarden van de verschoven bits bepalen.

Bit-adresseringEdit

Als de breedte van het register (vaak 32 of zelfs 64) groter is dan het aantal bits (meestal 8) van de kleinste adresseerbare eenheid (atomair element), vaak byte genoemd, leiden de verschuivingen tot een adresseringsschema op de bits.De grenseffecten aan beide uiteinden van het register buiten beschouwing latend, gedragen rekenkundige en logische verschuivingsoperaties zich hetzelfde, en een verschuiving met 8 bitposities transporteert het bitpatroon met 1 bytepositie op de volgende manier:

Ritmetische verschuivingEdit

Linker rekenkundige verschuiving

Rechter aritmetische verschuiving

In een aritmetische verschuiving, worden de bits die uit een van beide uiteinden zijn verschoven, weggegooid. Bij een aritmetische verschuiving naar links worden nullen naar rechts verschoven; bij een aritmetische verschuiving naar rechts wordt het tekenbit (de MSB in two’s complement) naar links verschoven, waardoor het teken van de operand behouden blijft.

Dit voorbeeld gebruikt een 8-bits register, geïnterpreteerd als two’s complement:

 00010111 (decimal +23) LEFT-SHIFT= 00101110 (decimal +46)

 10010111 (decimal −105) RIGHT-SHIFT= 11001011 (decimal −53)

In het eerste geval is het meest linkse cijfer voorbij het eind van het register geschoven, en is een nieuwe 0 naar de meest rechtse positie geschoven. In het tweede geval werd de meest rechtse 1 naar buiten verschoven (misschien naar de carry flag), en werd een nieuwe 1 naar de meest linkse positie gekopieerd, met behoud van het teken van het getal. Meervoudige verschuivingen worden soms verkort tot een enkele verschuiving met een aantal cijfers. Bijvoorbeeld:

 00010111 (decimal +23) LEFT-SHIFT-BY-TWO= 01011100 (decimal +92)

Een rekenkundige verschuiving naar links met n is gelijk aan vermenigvuldigen met 2n (mits de waarde niet overloopt), terwijl een rekenkundige verschuiving naar rechts met n van een two’s complement waarde gelijk is aan delen door 2n en afronden naar negatief oneindig. Als het binaire getal wordt behandeld als enencomplement, dan resulteert dezelfde verschuiving naar rechts in een deling door 2n en afronding naar nul.

Logische verschuivingEdit

Logische verschuiving naar links

logische verschuiving naar rechts

In een logische verschuiving, worden nullen naar binnen geschoven om de weggegooide bits te vervangen. Daarom zijn de logische en rekenkundige linkse verschuivingen precies hetzelfde.

Hoewel, aangezien de logische rechtse verschuiving waarde 0 bits in het meest significante bit invoegt, in plaats van het tekenbit te kopiëren, is het ideaal voor niet-ondertekende binaire getallen, terwijl de rekenkundige rechtse verschuiving ideaal is voor twee’s complement getekende binaire getallen.

Circulaire shiftEdit

Een andere vorm van shift is de circulaire shift, bitwise rotation of bitrotatie.

RotateEdit

Links circulair verschuiven of roteren

Rechts circulair verschuiven of rotate

In deze bewerking, ook wel rotate no carry genoemd, worden de bits “geroteerd” alsof de linker- en rechterkant van het register zijn samengevoegd. De waarde die bij een linkse verschuiving naar rechts wordt verschoven, is de waarde die er aan de linkerkant werd uitgeschoven, en vice versa bij een rechtse verschuiving. Dit is nuttig als het nodig is om alle bestaande bits te behouden, en wordt vaak gebruikt in digitale cryptografie.

Draaien door carryEdit

Links draaien door carry

Rechts draaiend doorvoeren

Rotate through carry is een variant van de rotate operatie, waarbij het bit dat wordt ingeschoven (aan een van beide uiteinden) de oude waarde van de carry-vlag is, en het bit dat wordt uitgeschoven (aan het andere uiteinde) de nieuwe waarde van de carry-vlag wordt.

Een enkele rotate through carry kan een logische of rekenkundige verschuiving van één positie simuleren door de carry-flag van tevoren in te stellen. Bijvoorbeeld, als de carry flag 0 bevat, dan is x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE een logische verschuiving naar rechts, en als de carry flag een kopie van de sign bit bevat, dan is x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE een rekenkundige verschuiving naar rechts. Om deze reden hebben sommige microcontrollers, zoals low-end PICs, alleen rotate en rotate through carry, en doen ze geen moeite met rekenkundige of logische verschuivingsinstructies.

Rotate through carry is vooral nuttig bij het uitvoeren van verschuivingen op getallen die groter zijn dan de native woordgrootte van de processor, want als een groot getal in twee registers wordt opgeslagen, moet het bit dat aan het ene eind van het eerste register wordt verschoven, aan het andere eind van het tweede register binnenkomen. Met rotate-through-carry wordt dat bit tijdens de eerste verschuiving “opgeslagen” in de carry-flag, klaar om tijdens de tweede verschuiving zonder extra voorbereiding naar binnen te schuiven.

In high-level languagesEdit

C-familieEdit

In C-familie talen zijn de logische verschuivingsoperatoren “<<” voor links verschuiven en “>>” voor rechts verschuiven. Het aantal te verschuiven plaatsen wordt als tweede argument aan de operator meegegeven. Bijvoorbeeld,

x = y << 2;

geeft x het resultaat van het verschuiven van y naar links met twee bits, wat gelijk staat aan een vermenigvuldiging met vier.

Shifts kunnen resulteren in implementatie-gedefinieerd gedrag of ongedefinieerd gedrag, dus wees voorzichtig bij het gebruik ervan. Het resultaat van een verschuiving met een aantal bits groter dan of gelijk aan de grootte van het woord is ongedefinieerd gedrag in C en C++. Het naar rechts verschuiven van een negatieve waarde is implementatie-afhankelijk en wordt niet aanbevolen door goede codeerpraktijken; het resultaat van het naar links verschuiven van een getekende waarde is ongedefinieerd als het resultaat niet kan worden gerepresenteerd in het resultatype.

In C# is de verschuiving naar rechts een rekenkundige verschuiving als de eerste operand een int of long is. Als de eerste operand van het type uint of ulong is, is de right-shift een logische shift.

Circulaire verschuivingenEdit

In de C-talenfamilie ontbreekt een rotatie-operator, maar er kan er een worden gesynthetiseerd uit de shift-operatoren. Er moet op gelet worden dat het statement goed gevormd is om ongedefinieerd gedrag en timing-aanvallen te voorkomen in software met beveiligingseisen. Bijvoorbeeld, een naïeve implementatie die een 32-bit unsigned waarde x naar links roteert door n posities is eenvoudigweg:

uint32_t x = ..., n = ...;uint32_t y = (x << n) | (x >> (32 - n));

Hoe dan ook, een verschuiving met 0 bits resulteert in ongedefinieerd gedrag in de rechter expressie (x >> (32 - n)) omdat 32 - 0 is 32, en 32 ligt buiten het bereik inclusief. Een tweede poging zou kunnen resulteren in:

uint32_t x = ..., n = ...;uint32_t y = n ? (x << n) | (x >> (32 - n)) : x;

waarbij het verschuivingsbedrag wordt getest om er zeker van te zijn dat het geen ongedefinieerd gedrag introduceert. De branch voegt echter een extra codepad toe en biedt een mogelijkheid voor timinganalyse en aanvallen, wat vaak niet acceptabel is in software met een hoge integriteit. Bovendien compileert de code naar meerdere machine instructies, wat vaak minder efficiënt is dan de native instructie van de processor.

Om het ongedefinieerde gedrag en branches onder GCC en Clang te vermijden, wordt het volgende aanbevolen. Het patroon wordt door veel compilers herkend, en de compiler zal een enkele rotate instructie emitteren:

uint32_t x = ..., n = ...;uint32_t y = (x << n) | (x >> (-n & 31));

Er zijn ook compilerspecifieke intrinsics die circulaire verschuivingen implementeren, zoals _rotl8, _rotl16, _rotr8, _rotr16 in Microsoft Visual C++. Clang biedt een aantal rotate intrinsics voor Microsoft compatibiliteit die te lijden hebben onder de bovenstaande problemen. GCC biedt geen rotate intrinsics. Intel biedt ook x86-intrinsics.

JavaEdit

In Java zijn alle integer-typen ondertekend, dus de operatoren “<<” en “>>” voeren rekenkundige verschuivingen uit. Java voegt de operator “>>>” toe om logische verschuivingen naar rechts uit te voeren, maar omdat de logische en rekenkundige links-verschuivingen identiek zijn voor signed integer, is er geen “<<<” operator in Java.

Meer details van Java shift operatoren:

• De operatoren << (shift links), >> (signed right shift), en >>> (unsigned right shift) worden de shift operatoren genoemd.
• Het type van de verschuivingsuitdrukking is het gepromoveerde type van de linker operand. Bijvoorbeeld, aByte >>> 2 is gelijkwaardig aan ((int) aByte) >>> 2.
• Als het gepromoveerde type van de linker operand int is, worden alleen de vijf laagste-orde bits van de rechter operand gebruikt als de verschuivingsafstand. Het is alsof de rechter operand wordt onderworpen aan een bitwise logische AND operator & met de maskerwaarde 0x1f (0b11111). De werkelijk gebruikte verschuivingsafstand ligt daarom altijd in het bereik van 0 tot en met 31.
• Als het gepromoveerde type van de linker operand lang is, dan worden alleen de zes laagste-orde bits van de rechter operand gebruikt als de verschuivingsafstand. Het is alsof de rechter operand wordt onderworpen aan een bitwise logische AND operator & met de maskerwaarde 0x3f (0b111111). De werkelijk gebruikte verschuivingsafstand ligt dus altijd in het bereik van 0 tot en met 63.
• De waarde van n >>> s is n naar rechts verschoven s bit-posities met nul-verlenging.
• Bij bit- en shift-bewerkingen wordt het type byte impliciet geconverteerd naar int. Als de byte-waarde negatief is, is de hoogste bit één, dan worden enen gebruikt om de extra bytes in de int op te vullen. Dus byte b1 = -5; int i = b1 | 0x0200; zal resulteren in i == -5.

JavaScriptEdit

JavaScript gebruikt bitwise operaties om elk van twee of meer eenheden plaats te evalueren naar 1 of 0.

PascalEdit

In Pascal, en ook in al zijn dialecten (zoals Object Pascal en Standard Pascal), zijn de logische linker en rechter shift operatoren respectievelijk “shl” en “shr“. Zelfs voor getekende gehele getallen gedraagt shr zich als een logische verschuiving, en kopieert het tekenbit niet. Het aantal te verschuiven plaatsen wordt gegeven als het tweede argument. Bijvoorbeeld, het volgende geeft x het resultaat van een verschuiving van y naar links met twee bits:

x := y shl 2;