Bitművelet

A digitális számítógépek programozása, illetve a digitális elektronika területén a bitművelet olyan művelet, amely egy vagy több bitsorozatot vagy bináris számot az egyes bitek szintjén manipulál. A bitművelet gyors, primitív tevékenység, amit a CPU közvetlenül támogat. Összehasonlítások és számítási műveletek elvégzésére használatos.

Olcsóbb, egyszerűbb processzorokon a bitműveletek nagyságrendekkel gyorsabbak az osztásnál, többször gyorsabbak a szorzás, és néha jelentősen gyorsabbak az összeadás műveleténél. Bár a modern processzorok hosszabb utasítás-futószalagjuknak és más mikroarchitekturális tervezési döntéseknek köszönhetően általában képesek ugyanolyan gyorsan elvégezni az összeadást vagy a szorzást mint a bitműveleteket, ezeken általában a bitműveletek kevesebb energiát fogyasztanak, mivel használatukhoz kevesebb erőforrásra van szükség.

Bitműveletek

Az alábbi példákban a bitek pozícióját jobbról (a legkevésbé értékes helyről) balra haladva adjuk meg. Például a bináris 0001 (decimális 1) minden helyi értékén nullákat tartalmaz, kivéve a legelsőn.

NOT (negáció, invertálás)

A bitszintű negálás vagy komplemensképzés egyváltozós művelet, ami minden biten logikai negációt hajt végre, az adott bináris érték egyes komplemensét képezve. Ahol az eredeti bit 0 volt, ott 1 lesz, ahol 1 volt, ott pedig 0. Például:

NOT 0111  (decimális 7)
  = 1000  (decimális 8)

A bitszintű negálás ekvivalens azzal, hogyha az eredeti bináris szám kettes komplemenséből levonunk egyet. Kettes komplemens-aritmetikában:

NOT x = −x − 1.

Előjel nélküli egészeknél egy szám bitszintű negáltja a szám „tükörképével” egyezik meg, ha az előjel nélküli egészek értékkészletének felezőpontjára tükrözünk. Például a 8 bites előjel nélküli egészeknél NOT x = 255 - x, ami grafikonon úgy nézne ki, mint egy lefelé induló egyenes ami a 0-255 tartományt megfordítja 255-0 irányban. Egyszerű, de látványos példa egy szürkeárnyalatos kép invertálása, ahol minden képpontot előjel nélküli számként tárolnak.

AND (logikai és, szorzás)

A bitszintű szorzás, ÉS művelet vagy AND két azonos hosszúságú bináris szám megfelelő bitpárjait sorban összeszorozva konjunkciót végez. Tehát ha a két szám azonos helyi értékén lévő mindkét bit 1 értékű, az eredményül kapott bináris számban is 1-es lesz azon a helyi értéken (1 × 1 = 1); egyébként az eredmény 0 (1 × 0 = 0). Például:

    0101 (decimális 5)
AND 0011 (decimális 3)
  = 0001 (decimális 1)

A művelet felhasználható annak eldöntésére, hogy a szám egy adott bitje (flagje) be van-e állítva (1) vagy törölve van-e (0). Például a 0011 bitmintán (decimális 3) határozzuk meg, hogy a második bit be van-e állítva! Ehhez a bitszintű ÉS műveletet használjuk úgy, hogy egy csak a második biten 1-esre állított értékkel szorozzuk össze:

    0011 (decimális 3)
AND 0010 (decimális 2)
  = 0010 (decimális 2)

Mivel az eredményül kapott 0010 nem nulla, tudjuk, hogy a második bit az eredeti bitmintában be volt állítva. Ezt a műveletet gyakran bitmaszkolásnak vagy maszkolásnak nevezik (annak analógiájára, ahogy festésnél öntapadós szalaggal takarják el a nem lefestendő területeket – ebben az esetben a 0 értékek takarják el a számunkra érdektelen biteket).

Ha egy eredményt kell tárolni, az ÉS művelet használható egy regiszter egyes bitjeinek törlésére. Például a 0110 (decimális 6) esetén a második bit törölhető egy bitszintű ÉS művelettel, ha olyan bitmintával végezzük el, aminek kizárólag a második bitje zérus:

    0110 (decimális 6)
AND 1101 (decimális 13)
  = 0100 (decimális 4)

Ennek a tulajdonságnak a felhasználásával könnyen ellenőrizhető egy bináris szám párossága, a legkisebb helyi értékű bit vizsgálatával:

    0110 (decimális 6)
AND 0001 (decimális 1)
  = 0000 (decimális 0)

Ezért 6 osztható 2-vel, tehát páros.

OR (logikai vagy, diszjunkció)

A bitszintű VAGY, illetve OR művelet két azonos hosszúságú bináris szám megfelelő bitpárjaival sorban logikai vagy műveletet, azaz diszjunkciót végez. Tehát ha a két szám azonos helyi értékén lévő bármelyik bit 1 értékű, az eredményül kapott bináris számban is 1-es lesz azon a helyi értéken, ha mindkét bit 0, akkor az eredmény is 0. Például:

   0101 (decimális 5)
OR 0011 (decimális 3)
 = 0111 (decimális 7)

A bitszintű vagy művelet felhasználható egy regiszter egyes bitjeinek beállítására. Például a 0010 (decimális 2) esetén a negyedik bit beállítható egy bitszintű VAGY művelettel, ha olyan bitmintával végezzük el, aminek kizárólag a negyedik bitje egyes:

   0010 (decimális 2)
OR 1000 (decimális 8)
 = 1010 (decimális 10)

Ezzel a technikával a lehető leghelytakarékosabban lehet Boole-algebrai értékeket tárolni.

XOR

A bitszintű kizáró vagy, illetve XOR két azonos hosszúságú bináris szám megfelelő bitpárjaival sorban kizáró vagy műveletet végez. Tehát ha a két szám azonos helyiértékén lévő bitek értéke megegyezik (mindkettő 1 vagy mindkettő 0), az eredmény 0, ha különbözőek (az első 1 és a második 0, vagy fordítva), akkor az eredmény 1. Például:

    0101 (decimális 5)
XOR 0011 (decimális 3)
  = 0110 (decimális 6)

A bitszintű XOR művelet felhasználható egy regiszter egyes kiválasztott bitjeinek átbillentésére (invertálására). Bármely bit értéke átbillenthető, ha 1-gyel XOR-oljuk. Például a 0010 (decimális 2) esetén a második és negyedik bit invertálható egy bitszintű kizáró vagy művelettel, ha olyan bitmintával végezzük el, aminek pontosan a második és a negyedik bitje egyes:

    0010 (decimális 2)
XOR 1010 (decimális 10)
  = 1000 (decimális 8)

Ezzel a technikával hatékonyan manipulálhatók a Boole-állapotokat reprezentáló bitsorozatok.

Assembly nyelven programozók az XOR-t arra is használják, hogy egy regiszter értékét nullára állítsák. Egy számot saját magával XOR-olva minden esetben nullát kapunk, és sok számítógép-architektúrán ez a művelet kevesebb órajelciklust/memóriát vesz igénybe mint a nulla értékének betöltése és regiszterbe mentése.

Matematikailag ekvivalens formulák

Feltéve, hogy $x>y$ , nemnegatív egész számokra a bitműveletek felírhatók a következő formában:

${\text{NOT }}x=\sum _{n=0}^{b}2^{n}\left[\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}+1\right){\bmod {2}}\right]$

$x{\text{ AND }}y=\sum _{n=0}^{b}2^{n}\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}\right)\left(\left\lfloor {\frac {y}{2^{n}}}\right\rfloor {\bmod {2}}\right)$

$x{\text{ OR }}y=\sum _{n=0}^{b}2^{n}\left[\left[\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}\right)+\left(\left\lfloor {\frac {y}{2^{n}}}\right\rfloor {\bmod {2}}\right)+\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}\right)\left(\left\lfloor {\frac {y}{2^{n}}}\right\rfloor {\bmod {2}}\right){\bmod {2}}\right]{\bmod {2}}\right]$

$x{\text{ XOR }}y=\sum _{n=0}^{b}2^{n}\left[\left[\left(\left\lfloor {\frac {x}{2^{n}}}\right\rfloor {\bmod {2}}\right)+\left(\left\lfloor {\frac {y}{2^{n}}}\right\rfloor {\bmod {2}}\right)\right]{\bmod {2}}\right]$

Ahol $b$ a bitek száma $x$ -ben, azaz $=\lfloor \log _{2}x\rfloor +1$ minden $x\neq 0$ esetre.

Biteltolások

A biteltolást (bit shift) is szokás bitműveletnek tekinteni, mivel nem számértékeken, hanem bitek sorozatán dolgozik. A biteltolás során a bináris számjegyek balra vagy jobbra tolódnak el („shift”-elődnek). Mivel a processzor regiszterei fix szélességűek, ezért egy vagy több bit ki fog shiftelődni a regiszter valamelyik végén, a másikon pedig ugyanannyi bit beshiftelődik; a biteltolási műveletek közötti különbséget épp az adja, hogy a beshiftelődő bitek értékét honnan vesszük.

Aritmetikai eltolás

Az aritmetikai eltolás esetében a bármely irányba kishiftelődő bitek értéke elveszik. Balra shiftelésnél nullák shiftelődnek be a jobb oldalon, jobbra történő aritmetikai eltolásnál pedig a jelzőbit (kettes komplemens esetén a legértékesebb helyi értékű bit, MSB) shiftelődik be a bal oldalon, megőrizve ezzel az operandus előjelét.

Az alábbi példa 8 bites regisztert tartalmaz:

   00010111 (decimális +23) LEFT-SHIFT
=  00101110 (decimális +46)

   10010111 (decimális −105) RIGHT-SHIFT
=  11001011 (decimális −53)

Az első esetben (eltolás balra) a balszélső számjegy kitolódik a regiszterből, és egy új 0 érkezik a jobbszélső pozícióba. A második esetben (eltolás jobbra) a jobbszélső 1 kitolódik (talán egy átvitel, azaz carry flagbe), és egy új 1 bit érkezik a balszélre, megtartva a szám előjelét. Egyes architektúrákon több eltolás összevonható egyszeri, több helyi értékkel történő eltolássá. Például:

   00010111 (decimális +23) LEFT-SHIFT-BY-TWO
=  01011100 (decimális +92)

Az n helyi értékkel történő aritmetikai balra shiftelés egyenértékű a 2ⁿ-nel szorzással (feltéve, ha nem történik közben túlcsordulás), az n helyi értékkel történő aritmetikai jobbra shiftelés pedig egyenértékű a 2ⁿ-nel való osztással és a negatív végtelen felé kerekítéssel. Ha a bináris számot egyes komplemens alakban vesszük, akkor ugyanez a jobbra shiftelés a 2ⁿ-nel való osztással és a nulla felé történő kerekítéssel egyenértékű.

Logikai eltolás

A logikai eltolás esetén nullák shiftelődnek be az eldobott bitek helyére, így a logikai és az aritmetikai eltolás balra tökéletesen megegyezik.

A logikai jobbra eltolás esetén viszont eltérés van, hiszen az előjelbit helyett minden esetben nulla értékű bit érkezik. Ezért a logikai eltolást előjel nélküli bináris számoknál, az aritmetikai eltolást előjeles, kettes komplemens alakú bináris számok esetében használják inkább.

Rotálás (körkörös eltolás) átvitel nélkül

Az eltolás egy másik fajtája a körkörös eltolás vagy rotálás. Ennek során a regiszter bitjei úgy rotálódnak, mintha a regiszter bal és jobb oldala össze lenne illesztve. A balra rotálás során jobb oldalra éppen az a bit érkezik meg, ami a bal oldalon kishiftelődött a regiszterből, és fordítva. Ez a művelet jól jön, ha szükség van az összes bit értékének megőrzésére, például a kriptográfiában is használják.

Rotálás (körkörös eltolás) átvitellel

A „rotálás átvitellel” művelet annyiban tér el a „rotálás átvitel nélkül” művelettől, hogy a regiszter két végét az átvitel jelzőbiten (carry flag) keresztül kötjük össze. A beshiftelődő bit minden esetben a carry flag régi értéke, a másik oldalon kishifelt bit pedig a carry flag új értékét adja.

A rotálás átvitellel művelet segítségével szimulálható a logikai vagy aritmetikai eltolás, amennyiben a carry flag előre be van állítva a megfelelő értékre. Például ha a carry flag értéke 0, akkor az x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE egy logikai eltolás jobbra, ha pedig a carry flag értéke megegyezik az előjelbitével, akkor az x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE egy aritmetikai eltolás jobbra. Épp ezért egyes olcsó PIC mikrokontrollerekben a rotálás és rotálás átvitellel utasítás megtalálható, de nem bajlódtak az aritmetikai vagy a logikai eltolás utasítások megvalósításával.

A rotálás átvitellel hasznos lehet a processzor natív szóhosszánál nagyobb bináris számokon végzett eltoláskor, mivel ha egy nagy számot két regiszterben kell tárolni, az első regiszter végéről kishiftelt bitet a másik regiszter elejére kell behozni. A rotálás átvitellel művelet ezt lehetővé teszi, hiszen a kérdéses bit elmentésre kerül az átvitel jelzőbitben az első rotálás során, amit a második rotáláskor minden külön előkészítés nélkül be lehet mozgatni.

Eltolások a C, C++, C#, Python nyelvekben

A C-ben és a C által ihletett nyelvekben, az eltolás balra és jobbra műveletek a következőek: „<<” és „>>”. Az eltolási operátorok második argumentumaként lehet megadni, hogy hány bittel történjen az eltolás. Például az

x = y << 2;

utasítás úgy ad értéket x-nek, hogy az y-t két bittel balra tolja el.

A C nyelvben a negatív érték jobbra történő eltolása implementációfüggő, előjeles érték balra eltolása pedig meghatározatlan értéket ad, ha az eredmény nem fejezhető ki az eredményváltozó típusának megfelelően.^[1] C#-ban a jobbra eltolás aritmetikai eltolásként végzendő el, ha az első operandus int vagy long típusú. Ha az első operandus uint vagy ulong, akkor pedig logikai eltolásként.^[2]

Fordítóprogramtól függően, specifikus módon történhet a körkörös eltolás kezelése, ahogy az a Microsoft Visual C++-ban a _rotl8, _rotl16, _rotr8, _rotr16 operátorokkal történik.

Eltolások Javában

A Java programozási nyelv minden egész típusa előjeles, a „<<” és „>>” operátorok aritmetikai eltolást végeznek. A Javában megjelenik a „>>>” operátor a logikai eltolás jobbra művelet elvégzéséhez, mivel azonban a logikai és aritmetikai eltolás balra operátorok megegyeznek, „<<<” operátor nem létezik a Javában.

A Java eltolási műveletinek további részletei:^[3]

A<< (left shift), >> (signed right shift) és >>> (unsigned right shift) operátorokat nevezikshift operator-oknak.
Az eltolási művelet eredménynek típusa a bal oldali operandus promotált típusával egyezik meg. Például aByte >>> 2 ugyanazt jelenti, mint ((int) aByte) >>> 2.
Ha a bal oldali operandus promotált típusa int, a jobb oldali operandusnak csak az öt legalacsonyabb értékű bitje használódik fel az eltolás számításánál. Ez úgy is tekinthető, mintha a jobb oldali operandus a művelet elvégzése előtt átesne egy bitszintű AND műveleten, aminél a maszkolás értéke 0x1f (0b11111).^[4] A tényleges eltolás mértéke ezért mindig a 0-31 bit tartományban marad.
Ha a bal oldali operandus promotált típusa long, a jobb oldali operandusnak csak a hat legalacsonyabb értékű bitje használódik fel az eltolás számításánál. Ez úgy is tekinthető, mintha a jobb oldali operandus a művelet elvégzése előtt átesne egy bitszintű AND műveleten, aminél a maszkolás értéke 0x3f (0b111111).^[4] A tényleges eltolás mértéke ezért mindig a 0-63 bit tartományban marad.
Az n >>> s értéke n jobbra eltolva s bitpozícióval, nullákkal kiegészítve.
Bitműveleteknél és eltolásoknál a byte típus implicit konvertálódikint típusra. Ha a bájt értéke negatív, tehát a legmagasabb helyi értékű bit 1-es, akkor 1-esekkel töltődnek fel az egész extra bájtjai. Ezért: byte b1=-5; int i = b1 | 0x0200; i == −5-öt ad eredményül.

Eltolások Pascalban

A Pascalban és annak dialektusaiban (mint az Object Pascal vagy a Standard Pascal), az eltolás balra és jobbra operátorok a „shl” és a „shr”. Az eltolási operátorok második argumentumaként lehet megadni, hogy hány bittel történjen az eltolás. Például a következő utasítás úgy ad értéket x-nek, hogy az y-t két bittel balra tolja el:

x := y shl 2;

Egyéb műveletek

popcount – a kriptográfiában használatos; beállított / nem nulla bitek száma egy adategységben, pl. gépi szóban, ld. Hamming-súly
vezető nullák száma – újabb processzorokban előforduló utasítás
záró nullák száma – az előző művelet egy változata

Alkalmazásai

A bitműveletek főleg alacsony szintű programozásnál szükségesek, például eszközmeghajtók írásánál, alacsony szintű grafikai programozásnál, kommunikációs protokollok csomagjainak összeállításánál és dekódolásánál.

Bár a számítógépek képesek aritmetikai és logikai műveletek hatékony elvégzésére, valójában az összes ilyen művelet összerakható bitműveletek és zérótesztelések kombinációból is.^[5] Az alábbi pszeudokódpélda az ókori egyiptomi szorzás megvalósítására tetszőleges a és b (a nagyobb mint b) között kizárólag bitszintű eltolásokat és összeadást használva:

c = 0

while b ≠ 0
    if (b and 1) ≠ 0
        c = c + a
    left shift a by 1
    right shift b by 1

return c

A következő példa az összeadás pszeudokód-implementációja kizárólag bitműveletek és zérótesztelés alkalmazásával:

while a ≠ 0
    c = b and a
    b = b xor a
    left shift c by 1
    a = c

return b

Az előbbi példákban az „=” nem az egyenlőségi relációt, hanem az értékadás műveletét jelöli.

Kapcsolódó szócikkek

Jegyzetek

↑ JTC1/SC22/WG14 N843 "C programming language" Archiválva 2022. augusztus 3-i dátummal a Wayback Machine-ben, section 6.5.7
↑ Operator (C# Reference). Microsoft. (Hozzáférés: 2013. július 14.)
↑ The Java Language Specification, section 15.19. Shift Operators
↑ ^a ^b JLS §15.22.1
↑ Synthesizing arithmetic operations using bit-shifting tricks. Bisqwit.iki.fi, 2014. február 15. (Hozzáférés: 2014. március 8.)

Fordítás

Ez a szócikk részben vagy egészben a Bitwise operation című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

További információk

Online Bitwise Calculator supports Bitwise AND, OR and XOR
Division using bitshifts
"Bitwise Operations Mod N" by Enrique Zeleny, Wolfram Demonstrations Project.
"Plots Of Compositions Of Bitwise Operations" by Enrique Zeleny, The Wolfram Demonstrations Project.

[1] JTC1/SC22/WG14 N843 "C programming language" Archiválva 2022. augusztus 3-i dátummal a Wayback Machine-ben, section 6.5.7

[2] Operator (C# Reference). Microsoft. (Hozzáférés: 2013. július 14.)

[3] The Java Language Specification, section 15.19. Shift Operators

[jls15.22.1-4] JLS §15.22.1

[5] Synthesizing arithmetic operations using bit-shifting tricks. Bisqwit.iki.fi, 2014. február 15. (Hozzáférés: 2014. március 8.)

[1]

[2]

[3]

[4]

[5]