Bitművelet

A Wikipédiából, a szabad enciklopédiából
Jump to navigation Jump to search

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[szerkesztés]

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)[szerkeszté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 (logika és, szorzás)[szerkeszté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ó)[szerkesztés]

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[szerkesztés]

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[szerkesztés]

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[szerkesztés]

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[szerkesztés]

Aritmetikai eltolás balra
Aritmetikai eltolás jobbra

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[szerkesztés]

Logikai eltolás balra
Logikai eltolás jobbra

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[szerkesztés]

Körkörös eltolás vagy rotálás balra
Körkörös eltolás vagy rotálás jobbra

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[szerkesztés]

Rotálás balra átvitelbittel
Rotálás jobbra átvitelbittel

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[szerkesztés]

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[szerkesztés]

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[szerkesztés]

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;

Alkalmazásai[szerkesztés]

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[szerkesztés]

Jegyzetek[szerkesztés]

  1. JTC1/SC22/WG14 N843 "C programming language", 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
  4. ^ a b 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.)

Fordítás[szerkeszté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.

További információk[szerkesztés]