Tamás Ferenc: Bitenkénti műveletek

 

A látszat ellenére ez a cikk nem kizárólag matematikával foglalkozik, bár a lényege mégis a matematika lesz. Az alapok igen egyszerűek, utána már nem árt kicsit gondolkodni is!

A legegyszerűbb bitenkénti műveletek az úgynevezett logikai alapműveletek: tagadás (NOT), és (AND), vagy (OR). Sokan ide sorolják a kizáró vagy (XOR) műveletet is. Vegyük ezeket, illetve az igazságtábláikat sorra!

Negáció – tagadás – NOT:

Kiindulás

Eredmény

igaz (1)

hamis (0)

hamis (0)

igaz (1)

Bitenkénti NOT

Az alapvető logikai műveletek közül ez az egyetlen, ami csak egy operátorral rendelkezik és egyben ez a legegyszerűbb is. Halmazelméleti jele: Ā. Gyakori matematikai jele: Több programozási nyelvben is elterjedt szimbóluma: !A.

Konjunkció – logikai ÉS – AND:

A

B

A AND B

igaz (1)

igaz (1)

igaz (1)

igaz (1)

hamis (0)

hamis (0)

hamis (0)

igaz (1)

hamis (0)

hamis (0)

hamis (0)

hamis (0)

Bitenkénti AND

Ez a művelet akkor és csak akkor lesz igaz, ha mindkettő bemeneti értéke igaz. Halmazelméleti jele: . Több programozási nyelvben elterjedt szimbóluma: A&B, esetleg A&&B.

Diszjunkció – logikai VAGY – OR:

A

B

A OR B

igaz (1)

igaz (1)

igaz (1)

igaz (1)

hamis (0)

igaz (1)

hamis (0)

igaz (1)

igaz (1)

hamis (0)

hamis (0)

hamis (0)

Bitenkénti OR

Ez a művelet akkor és csak akkor lesz hamis, ha mindkettő bemeneti adata hamis. Halmazelméleti jele: . Több programozási nyelvben elterjedt szimbóluma: AǁB. Egyes programozási nyelvekben A|B is megengedett. Ilyen esetekben ha a bal oldali állítás hamis, akkor már nem is vizsgálja tovább a végrehajtó program az állítást, hiszen ez már eleve hamis lesz.

Antivalencia – kizáró VAGY – XOR:

A

B

A XOR B

igaz (1)

igaz (1)

hamis (0)

igaz (1)

hamis (0)

igaz (1)

hamis (0)

igaz (1)

igaz (1)

hamis (0)

hamis (0)

hamis (0)

Bitenkénti XOR

Ez a hétköznapi értelemben nehezen értelmezhető művelet akkor és csak akkor igaz, ha pontosan csak az egyik bemeneti változó igaz, azaz a másik hamis. Halmazelméleti jele: A⊕B. Több programozási nyelvben elterjedt szimbóluma: A XOR B.

(Az ábrák származási helye: Geogebra.org online verziója)


Az alapvető logikai műveletek után jöjjenek a kicsit bonyolultabbak! Első sorban meg kell ismerkednünk a több bemenetű logikai műveletekkel. Első példánkban például vizsgáljuk meg, hogy mikor lesz igaz a következő állítás: A & (B ǁ C).

Ehhez kicsit bonyolultabb igazságtáblázatra lesz szükségünk, mivel három bemeneti változó kell, így összesen 23=8 esetet kell vizsgálni. Elsőnek vegyük fel a nyolcféle alaplehetőséget.

A

B

C

BǁC

A&(BǁC)

1 1 1    
1 1 0    
1 0 1    
1 0 0    
0 1 1    
0 1 0    
0 0 1    
0 0 0    

Most töltsük ki a negyedik oszlopot, tehát a B OR C értékét.

A

B

C

BǁC

A&(BǁC)

1 1 1 1  
1 1 0 1  
1 0 1 1  
1 0 0 0  
0 1 1 1  
0 1 0 1  
0 0 1 1  
0 0 0 0  

Utoljára azt vizsgáljuk, hogy ez a 4. oszlop és a legelső (A) oszlop közötti hogyan alakul az AND művelet.

A

B

C

BǁC

A&(BǁC)

1 1 1 1 1
1 1 0 1 1
1 0 1 1 1
1 0 0 0 0
0 1 1 1 0
0 1 0 1 0
0 0 1 1 0
0 0 0 0 0

Összességében tehát látható, hogy a fenti művelet csak az első három esetben lesz igaz.


Most jöjjön egy kicsit bonyolultabb összefüggés! Vizsgáljuk meg, hogy mikor igaz a következő kifejezés:

((A & B)||(C⊕A))&B.

Vegyük észre, hogy itt az A & B értékét kétszer is igénybe vesszük. Az értéktáblázatunk legyen az előzőhöz hasonló! Az alapértékekkel egyből töltsük is ki.

A

B

C

         
1 1 1          
1 1 0          
1 0 1          
1 0 0          
0 1 1          
0 1 0          
0 0 1          
0 0 0          

Első lépésben legyen meg az A&B művelet.

A

B

C

A&B

       
1 1 1 1        
1 1 0 1        
1 0 1 0        
1 0 0 0        
0 1 1 0        
0 1 0 0        
0 0 1 0        
0 0 0 0        

Most jöjjön a C⊕A.

A

B

C

A&B

C

     
1 1 1 1 0      
1 1 0 1 1      
1 0 1 0 0      
1 0 0 0 1      
0 1 1 0 1      
0 1 0 0 0      
0 0 1 0 1      
0 0 0 0 0      

Most jöjjön az utolsó két oszlop összekapcsolása egy VAGY művelettel.

A

B

C

A&B

C⊕A

(A & B) || (C⊕A)

   
1 1 1 1 0 1    
1 1 0 1 1 1    
1 0 1 0 0 0    
1 0 0 0 1 1    
0 1 1 0 1 1    
0 1 0 0 0 0    
0 0 1 0 1 1    
0 0 0 0 0 0    

Bár nem kötelező, de célszerű ide másolni a B oszlopát, mivel így könnyebb lesz a végső műveletsor.

A

B

C

A&B

C

(A & B) || (C⊕A)

B

 
1 1 1 1 0 1 1  
1 1 0 1 1 1 1  
1 0 1 0 0 0 0  
1 0 0 0 1 1 0  
0 1 1 0 1 1 1  
0 1 0 0 0 0 1  
0 0 1 0 1 1 0  
0 0 0 0 0 0 0  

Most jöjjön az utolsó két oszlop összekapcsolása ÉS művelettel.

A

B

C

A&B

C

(A & B) || (C⊕A)

B

vége

1 1 1 1 0 1 1 1
1 1 0 1 1 1 1 1
1 0 1 0 0 0 0 0
1 0 0 0 1 1 0 0
0 1 1 0 1 1 1 1
0 1 0 0 0 0 1 0
0 0 1 0 1 1 0 0
0 0 0 0 0 0 0 0

A fentiek alapján már elég bonyolult számításokat, illetve műveletsorokat is elvégezhetünk!


Most jöjjön két olyan művelet, amit elég gyakran emlegetnek, de nem tartoznak az alapvető műveletek közé.

Shift-to-left - Bitenkénti balra tolás – S2L:

Az egyszerűség kedvéért ezt nézzük meg egy bájton ábrázolva!

0 0 0 1 0 0 1 0

 

eltolva balra:

0 0 1 0 0 1 0

x

 

 

Látható, hogy az egyes bitek balra egyet eltolódnak, de az utolsó bit így bizonytalan lesz, mivel tőle balra nem volt kiindulási bit. Így az utolsó bitet többnyire 0-val töltik fel a rendszerek. A gyakorlatban egész számok esetén ez kettővel való szorzást jelent, ha nem vesszük bele az előjeles egész számoknál előforduló előjelbitet, ami rendszerint az első bájt legelső bitje.

Shift-to-right – Bitenkénti jobbra tolás – S2R:

Ez a művelet az előző eltolásnak éppen az ellentettje lesz. Legyen itt is az alapeset ugyanaz:

0 0 0 1 0 0 1 0

 

 

Eltolva jobbra a következőt kapjuk:

x

0 0 0 1 0 0 1

 

 

Ismételten látható, hogy az egyes bitek eltolódnak, de a legelső bit megint bizonytalan lesz, mivel ott nem volt kiindulási bit. Az előjel nélküli egész számok esetén ez a bit 0 lesz, de egyes negatív számok esetén előfordulhat, hogy kiegészítés a helyes érték-ábrázolás miatt 1-es lesz. A gyakorlatban ez az egész számok esetén kettővel való osztást jelent – persze ismételten kivételt jelent az előjelbit.

A fenti két bitenkénti műveletet a gyakorlatban akkor használják a számítógépek, ha kettő hatványát kell előállítani villámgyorsan. Például a 16-ot úgy is lehet ábrázolni, hogy a gép alapvetően 1-es rak a megfelelő memóriarekeszbe, majd 4-szer eltolja balra. Más problémát jelent a 20 ábrázolása, mivel itt a 16-ot kell összeadni a hasonlóan képzett 4-gyel. Ezzel már el is jutottunk a következő műveletig, az összeadásig.


Addíció – Összeadás – ADD:

Legyen adott két tetszőlege egész szám (max. 8 biten), amelyeket szeretnénk összeadni. Ehhez tudni kell a megfelelő bit-műveleteket, de ezek igen egyszerűek:

0+0 = 0.

0+1 = 1.

1+0 = 1.

1+1 = 0, de keletkezik egy átvitel.

Nos, ez igen egyszerűen hangzik, de a gyakorlatban egy kicsit bonyolultabb.

Legyen a két szám az 5 és a 16, tehát:

Érték

128

64

32

16

8

4

2

1

Átvitel

0 0 0 0 0 1 0 1
  0 0 0 1 0 0 0 0

Összeg:

               

Láthatjuk, hogy itt az összegben sehol sem lesz átvitel, tehát ez még egyszerű eset lesz:

Érték

128

64

32

16

8

4

2

1
  0 0 0 0 0 1 0 1
  0 0 0 1 0 0 0 0

Összeg:

0 0 0 1 0 1 0 1

Ezt visszafejtve 21-et kapunk. A következő számítás már legyen egy bonyolultabb. A két szám legyen 31, illetve 133.

Érték

128

64

32

16

8

4

2

1
  0 0 0 1 1 1 1 1
  1 0 0 0 0 1 0 1

Összeg:

               

Az összeg képződésénél már a legelső biten lesz átvitel.

Érték

128

64

32

16

8

4

2

1
  0 0 0 1 1 1 1 1
  1 0 0 0 0 1 0 1

Összeg:

             

0+átv.

Így a 2-es helyiérték oszlopához még 1-es hozzá kell adni. Tehát e helyes eredmény: 1+0+1(átvitel)=0 + átvitel lesz.

Érték

128

64

32

16

8

4

2

1

Átvitel

0 0 0 1 1 1 1 1
  1 0 0 0 0 1 0 1

Összeg:

           

0+átv.

0

Most a 4-es oszlopához érve láthatjuk, hogy 1+1+1(átvitel) lesz, ami 1+1(átvitel) lesz.

Érték

128

64

32

16

8

4

2

1
  0 0 0 1 1 1 1 1
  1 0 0 0 0 1 0 1

Összeg:

         

1+átv.

0 0

Tehát ez az átvitel már a 8-as oszlopban lesz, ami így 1+0+1(átvitel) = 0+átvitel lesz.

Érték

128

64

32

16

8

4

2

1
  0 0 0 1 1 1 1 1
  1 0 0 0 0 1 0 1

Összeg:

       

0+átv.

1 0 0

Ugyanez érvényesül a 16-os oszlopban is, de a 32-es oszlopban már csak egy darab átvitel lesz a két darab 0 mellett, így itt már nem keletkezik átvitel. Tehát a helyes végeredmény a következő lesz:

Érték

128

64

32

16

8

4

2

1
  0 0 0 1 1 1 1 1
  1 0 0 0 0 1 0 1

Összeg:

1 0 1 0 0 1 0 0

Az összeget visszafejtve láthatjuk, hogy 128+32+4=164, ami éppen 31+133. Tehát a művelet helyes volt.

Most a következőre próbáljuk meg összeadni a 132-t és a 133-at.

Érték

128

64

32

16

8

4

2

1
  1 0 0 0 0 1 0 0
  1 0 0 0 0 1 0 1

Összeg:

               

Itt már az eddig tanultak szerint egyszerű lesz a dolgunk, hiszen csak a 4-es oszlopban lesz átvitel – egészen addig, amíg el nem jutunk a 128-as oszlopig.

Érték

128

64

32

16

8

4

2

1
  1 0 0 0 0 1 0 0
  1 0 0 0 0 1 0 1

Összeg:

?...?

0 0 0 1 0 0 1

Egyértelmű, hogy a 128-as oszlopban is keletkezik egy átvitelbit, de ez már nem fér bele az eddig megszokott egyetlen bitbe, tehát egy túlcsordulás keletkezik. Így a végeredmény:

Érték

128

64

32

16

8

4

2

1
  1 0 0 0 0 1 0 0
  1 0 0 0 0 1 0 1

Összeg:

0+

túlcsordulás

0 0 0 1 0 0 1

Könnyű belátni, hogy ezt az esetet a legtöbb számítógépes programnak is kezelnie kell, de éppen ezért a programozási nyelvek döntő többségében az egész számok 16 biten értelmezettek, amiből csak a legelső az előjelbit, így a tényleges 15 biten 32768 lesz ábrázolható. Ez a hétköznapi számolásokra elegendő. Ettől függetlenül sok nyelv kínál ún. hosszú egészeket vagy duplapontos egészeket, amik már nyelvtől függően 31, vagy több biten ábrázolhatóak.


Végezetül szeretném megköszönni Pencsné Mészáros Erzsébet kolleginámnak, hogy végigellenőrizte a cikk számolásait!

Tisztelt Olvasó! Kérem, írja meg véleményét, hozzászólását, illetve kiegészítését a szokásos tferi(kukac)tferi(pont)hu címre.

© TFeri.hu, 2016.
Felújítva: 2017 és 2021.