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 , nemnegatív egész számokra a bitműveletek felírhatók a következő formában:
Ahol a bitek száma -ben, azaz minden 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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/5c/Rotate_left_logically.svg/150px-Rotate_left_logically.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/37/Rotate_right_arithmetically.svg/150px-Rotate_right_arithmetically.svg.png)
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 2n-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 2n-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 2n-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
- Boole-algebra (informatika)
- Karnaugh-tábla
- Logikai kapu
- Logikai művelet
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.