Kettes számrendszer

A kettes számrendszer vagy bináris számrendszer olyan helyiérték-jelölő számrendszer, ami két számjeggyel ábrázolja a számokat, az arab számírásban a 0-s és az 1-es jegyekkel. Mivel digitális áramkörökben a számrendszerek közül a kettest a legegyszerűbb megvalósítani, a modern számítógépekben és gyakorlatilag bármely olyan elektronikus eszközben, amely valamilyen számításokat végez, szinte kivétel nélkül ezt használják.

Története

Táblázat Leibniz alapművéből

A kettes számrendszer pontos leírását először Gottfried Wilhelm Leibniz adta meg az 1703-ban megjelent Explication de l'Arithmétique Binaire című könyvében.

1854-ben George Boole megjelentetett egy cikket a később Boole-algebra néven ismertté váló logikai rendszerről. A cikk mérföldkő volt a logika történetében, és létfontosságú a bináris aritmetika áramkörökkel való megvalósításában.

1937-ben Claude Shannon megírta A Symbolic Analysis of Relay and Switching Circuits című, a Boole-algebra és a bináris aritmetika kapcsolókkal és relékkel való megvalósítását leíró diplomamunkáját a Massachusetts Institute of Technology-n, és ezzel megalapozta a digitális áramkörök elméletét.

1946-ban a Neumann János által megalkotott Neumann-elvek között szerepel a kettes számrendszer mint a számítások számrendszere.

Számolás kettes számrendszerben

A tízes számrendszerhez hasonlóan a kettes számrendszerben is elvégezhetők a szokásos alapműveletek. Az ehhez szükséges algoritmusok egyszerűbbek, és hatékonyan valósíthatók meg logikai áramkörökkel. A kettes számrendszer bevezetése több előnnyel is járt a számítástechnikában.

Összeadás Példa 0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 10 ${{\begin{array}{cr}&1011_{2}\\+&11_{2}\\\end{array}} \over {\begin{array}{cr}\ \ \ \ &1110_{2}\\\end{array}}}$	Kivonás Példa 0 − 0 = 0 0 − 1 = −1 1 − 0 = 1 1 − 1 = 0 ${{\begin{array}{cr}&1011_{2}\\-&111_{2}\\\end{array}} \over {\begin{array}{cr}&\ \ \ \ 100_{2}\end{array}}}$
Szorzás Példa 0 $\cdot$ 0 = 0 0 $\cdot$ 1 = 0 1 $\cdot$ 0 = 0 1 $\cdot$ 1 = 1 ${{\begin{array}{cr}&1010_{2}\\\cdot &11_{2}\\\end{array}} \over {\begin{array}{cr}&11110_{2}\end{array}}}$	Osztás Példa 0 / 0 = n.def.* 0 / 1 = 0 1 / 0 = n.def.* 1 / 1 = 1 ${{\begin{array}{cr}&1010_{2}\\/&10_{2}\\\end{array}} \over {\begin{array}{cr}&\ \ \ \ 101_{2}\end{array}}}$

*: nincs definiálva

Összeadás

$A$	$B$	$M_{1}$		$M_{2}$	$E$
0	0	0		0	0
0	0	1		0	1
0	1	0		0	1
0	1	1		1	0
1	0	0		0	1
1	0	1		1	0
1	1	0		1	0
1	1	1		1	1

A kettes számrendszerbeli összeadás a számítógépek világának legalapvetőbb művelete. Az A és a B pozitív számok úgy adhatók össze, mint a tízes számrendszerben, csak arra kell ügyelni, hogy az összegben nem jelenik meg a kettes (vagy a hármas). Ehelyett átvitel keletkezik, a tízes számrendszerbeli tízestúllépéshez hasonlóan.

A táblázatban M₁ jelöli a meglevő, és M₂ a keletkező átvitelt.

Kivonás

A kivonás az összeadáshoz hasonlóan viselkedik.

0 − 0 = 0

0 − 1 = −1 (a különbség 1, átvitel 1)

1 − 0 = 1

1 − 1 = 0

0 - 1 1 átvitellel = 0 az átvitel 1

1 - 1 1 átvitellel = 1 az átvitel 1

A számítógépek a kivonást a kettes komplemens segítségével végzik. A kisebbítendőhöz hozzá kell adni a kivonandó kettes komplementerét. Ez két lépést jelent. Át kell váltani a kivonandót kettes számrendszerbe, majd a bitjeit át kell billenteni, majd 1-et hozzá kell adni. Az így kapott számot és a kisebbítendő bináris számát össze kell adni. például vonjuk ki a 8-ból az 5-öt.

8 − 5 = 3

8:     1000
5:     0101
5 I:   1010 (bitek átbillentve)
5 II:  1011 (+1)

Ezeket most össze kell adni:

 1000
+1011
−−−−−
10011

A kapott eredmény az 10011. Itt viszont keletkezik egy felesleges bit, túlcsordulás, amit le kell választani, arra nincs szükség.

1 | 0011

Az így kapott számot, ha visszaváltjuk 10-es számrendszerbe, akkor megkapjuk az eredményt.

0011 = 1 + 2 = 3

Szorzás

A kettes számrendszerben hasonlóan lehet szorozni, mint tízes számrendszerben. Lényegesen egyszerűsíti a dolgokat, hogy csak 1 és 0 fordul elő számjegyekként. Arra kell ügyelni, hogy amikor a részszorzatokat összeadjuk, akkor kettes számrendszerben adunk össze.

Áramköri szinten a szorzást is összeadó áramkörök valósítják meg, kihasználva, hogy a szorzás művelete lebontható sorozatos összeadásokra. Például a decimális 3 × 4 = 12 (= 4 + 4 + 4) kifejezést binárisra átírva kapjuk:

0011 × 0100 = 0100 + 0100 + 0100 = 1100.

Osztás

A tízes számrendszerhez hasonlóan lehet osztani. Ha az osztó nem kettőhatvány, akkor a hányados periodikus kettedestört lesz. A pontos érték ismeretéhez egy előszakasz + periódusig kell osztani.

A számítógépek csak egy bizonyos pontosságig végzik el ezt a műveletet.

Hasonlóan lehet maradékosan is osztani.

Az osztás műveletet először kivonások – majd összeadások – sorozatára bontjuk, a kivonásokat addig folytatjuk, amíg a kisebbítendő egyenlő vagy kisebb nem lesz a kivonandónál.

Például a decimális 8/2 = 4 ( 8 − 2 − 2 − 2 − 2 ). Az osztandóból kisebbítendő, az osztóból kivonandó lesz.

Osztás összeadással: 11/4 = 2,75 ( 2x4 + 7x0,4 + 5x0,04 ). 1011/0100 = 10,11. A hányados 1-es helyiértékeivel vissza szorozva 10x0100 + 0.1x0100 + 0.01x0100 = 1011, ezzel megkaptuk az eredeti osztandónkat. Tehát az osztásból úgy lesz összeadás, hogy számoljuk hányszor tudjuk csökkenteni az osztandót az osztóval úgy, hogy a hányados ne legyen kisebb 0-nál, ha pont nullát kapnánk akkor vége a tevékenységnek, az eredmény a lépések száma. Ellenkező esetben maradékos osztásról van szó, és a maradékok helyiértékenként csökkenve állnak elő.

Az egészrészt megkaptuk az eddigi lépések összegeként, a tört rész úgy adódik, hogy az első negatív eredményű kivonásnál egy új lépést iktatunk be, majd az egész tevékenység kezdődik elölről. Ez az új lépés az, hogy a maradékot egy helyiértékkel balra toljuk – a számrendszer alapszámával beszorozzuk -, a fenti példából 11 − 4 = 7, 7 − 4 = 3, 3 − 4 = −1. 2 lépés, az egészrész 2.

Az utolsó lépés már negatív eredményt ad, nekünk a 3 a legkisebb nem negatív maradék, ezért ezt balra shifteljük (10-zel szorozzuk) és folytatjuk az eljárást azzal, hogy az új osztandónk a 30 lesz, az osztó nem változik viszont az eredményünk majd egy helyiértékkel kisebb, a törtrész első tagja lesz. 30 − 4 = 26, 26 − 4 = 22, 22 − 4 = 18, 18 − 4 = 14, 14 − 4 = 10, 10 − 4 = 6, 6 − 4 = 2, 2 − 4 = −2. 7 lépés, a törtrész első, legnagyobb helyiértéke 7. A legkisebb nem negatív maradék a 2 volt, shifteljük balra, az osztandónk most 20, osztó marad 4, az eredmény helyiértéke ismét csökken eggyel. 20 − 4 = 16, 16 − 4 = 12, 12 − 4 = 8, 8 − 4 = 4, 4 − 4 = 0. 5 lépés, tehát a maradék második tagja 5, így az eredmény: 2,75.

A példa az egyszerűbb megértésért tízes számrendszerben, kivonásokkal mutatja be az osztás lebontását összeadásokra, de természetesen ez binárisan és kivonások helyett kettes komplementer összeadásokkal zajlik.

Átváltás

Kettes számrendszerből tízes számrendszerbe

A kettes számrendszer helyiértékes számrendszer: jobbról balra haladva minden egyes számjegy a 2 eggyel nagyobb hatványát fejezi ki (2⁰ = 1-től kezdve). A kettes számrendszerben ábrázolt szám értékét úgy kapjuk meg, hogy összeadjuk azokat a kettő-hatványokat, amelyek helyiértékénél 1 áll. Például:

1010011011₂ =

=1·2⁹ + 0·2⁸ + 1·2⁷ + 0·2⁶ + 0·2⁵ + 1·2⁴ + 1·2³ + 0·2² + 1·2¹ + 1·2⁰ =

= 2⁹ + 2⁷ + 2⁴ + 2³ + 2¹ + 2⁰ =

= 512 + 128 + 16 + 8 + 2 + 1 = 667

Tízes számrendszerből kettes számrendszerbe

Egy N szám kettes számrendszerben ábrázolt értékét a következő algoritmussal kaphatjuk meg:

1. Megkeressük azt a d legnagyobb kettő-hatványt, ami nem nagyobb, mint N (ez éppen 2^{$[\log _{2}(N)]$} lesz).
2. Ha d nem nagyobb, mint N, akkor N := N − d és leírunk (az előző leírt számjegytől jobbra) egy 1-et; ha nagyobb, akkor leírunk egy 0-t.
3. Ha d = 1, akkor az algoritmus véget ért.
4. d := d/2
5. Ugrás a 2. lépésre.

Egy másik módszer, a sorozatos osztás módszere:

Ahelyett, hogy egyből a lehető legnagyobb hatványt vonnánk ki, az új alappal osztunk sorozatosan, így a kisebb egységektől haladunk a nagyobbak felé. A maradékok az egyre nagyobb egységek számát jelzik. Előnye, hogy nem kell előre megbecsülni, hogy mekkora a lehető legnagyobb hatvány, ami még nem kisebb az adott számnál.

Az eredeti számot maradékosan osztjuk kettővel, így megkapjuk, hány kettes lenne benne. A maradék az egyesek számát adja. Megnézzük, hogy van-e elég kettes ahhoz, hogy egy nagyobb egységet képezzen. Ha van, akkor egy maradékos osztással megkapjuk, hány kettest nem lehet egy nagyobb egységre beváltani. Ismételjük az osztásokat, amíg nem kapunk nullát vagy egyet. Ez lesz a kettes számrendszerbe átírt szám első jegye, bitje. A többi jegyét fordított sorrendben adják a maradékok.

Példa:

$\left.{\begin{array}{rcccrcc}41&:&2&=&20,&{\text{ marad }}&\mathbf {1} \\20&:&2&=&10,&{\text{ marad }}&\mathbf {0} \\10&:&2&=&5,&{\text{ marad }}&\mathbf {0} \\5&:&2&=&2,&{\text{ marad }}&\mathbf {1} \\2&:&2&=&1,&{\text{ marad }}&\mathbf {0} \\1&:&2&=&0,&{\text{ marad }}&\mathbf {1} \end{array}}\;\;\right\Uparrow$

Gyors hatványozás

A kettes számrendszernek nagy jelentősége van a gyors hatványozásban. Egy n^k hatvány (k kettes számrendszerbeli alakjának ismeretében) kiszámítható legfeljebb 2·log(k) szorzással a következő módon:

1. N := 1, d := n, i := 0;
2. ha k-nak az i-edik helyiértékén 1 van, akkor N := N · d;
3. ha az i a k legnagyobb helyiértékét jelölte, az algoritmus véget ért;
4. i := i + 1; d := d · d;
5. ugrás a 2. lépésre.

Források

• Stoyan Gisbert - Takó Galina: Numerikus módszerek 1.
• Leibniz és a kettes számrendszer
• binaersystem.homeunix.org, Oldal a kettes számrendszerről
• Számrendszerek átváltása (u. a. dual ↔ dezimal)
• Összefoglalás a számrendszerekről és a kettes számrendszerben számolásról
• Nem egész számok átváltása kettesszámrendszerbe

Kapcsolódó szócikkek

• Bit
• Számrendszerek az informatikában
• Binárisan kódolt decimális

További információk

• Alice és Bob - 3. rész: Alice és Bob számolni tanul