Kettes számrendszer

A Wikipédiából, a szabad enciklopédiából

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[szerkesztés | forrásszöveg szerkesztése]

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

A kettes számrendszer pontos leírását először Gottfried 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 MIT-en, é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[szerkesztés | forrásszöveg szerkesztése]

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{matrix}
                    &1011_2\\
\operatorname{+}&\ \ \ 11_2\\
\end{matrix}
\over
\begin{matrix}
                &\ \ 1110_2\\
\end{matrix}}
Kivonás Példa
0 − 0 = 0

0 − 1 = −1
1 − 0 = 1
1 − 1 = 0


\begin{matrix}
&1011_2\\
{-\ }&\ \ 111_2\\
\end{matrix}
\over
\begin{matrix}
&\ \ \ \ \ 100_2
\end{matrix}
Szorzás Példa
0 \cdot 0 = 0

0 \cdot 1 = 0
1 \cdot 0 = 0
1 \cdot 1 = 1


\begin{matrix}
&1010_2\\
{\cdot}&\ \ \ 11_2\\
\end{matrix}
\over
\begin{matrix}
&11110_2
\end{matrix}
Osztás Példa
0 / 0 = n.def.

0 / 1 = 0
1 / 0 = n.def.
1 / 1 = 1


\begin{matrix}
&1010_2\\
{/}&\ \ \ 10_2\\
\end{matrix}
\over
\begin{matrix}
&\ \ \ 101_2
\end{matrix}

Összeadás[szerkesztés | forrásszöveg szerkesztése]

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ízes túllépéséhez hasonlóan.

A táblázatban M_1 jelöli a meglevő, és M_2 a keletkező átvitelt.

Kivonás[szerkesztés | forrásszöveg szerkesztése]

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 5 II: 1011

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 vissza váltjuk 10-es számrendszerbe, akkor megkapjuk az eredményt. 0011 = 1+2 = 3

Szorzás[szerkesztés | forrásszöveg szerkesztése]

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 3x4=12 (4+4+4) kifejezést binárisra átírva kapjuk: 0011 x 0100 = 0100 + 0100 + 0100 = 1100

Osztás[szerkesztés | forrásszöveg szerkesztése]

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 mí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 ). 1101/0100 = 10,11. A hányados 1-es helyiértékeivel vissza szorozva 10x0100 + 0.1x0100 + 0.01x0100 = 1101, 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őrö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-el 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[szerkesztés | forrásszöveg szerkesztése]

Kettes számrendszerből tízes számrendszerbe[szerkesztés | forrásszöveg szerkesztése]

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 (20=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:

10100110112 = 1·29 + 0·28 + 1·27 + 0·26 + 0·25 + 1·24 + 1·23 + 0·22 + 1·21 + 1·20 = 29 + 27 + 24 + 23 + 21 + 20 = 512 + 128 + 16 + 8 + 2 + 1 = 667

Tízes számrendszerből kettes számrendszerbe[szerkesztés | forrásszöveg szerkesztése]

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 2-re.

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{matrix}
 41 &: 2 &=& 20 &\mathrm{ marad }\ \ \mathbf{1}\\
 20 &: 2 &=& 10 &\mathrm{ marad }\ \ \mathbf{0}\\
 10 &: 2 &=&  5 &\mathrm{ marad }\ \ \mathbf{0}\\
  5 &: 2 &=&  2 &\mathrm{ marad }\ \ \mathbf{1}\\
  2 &: 2 &=&  1 &\mathrm{ marad }\ \ \mathbf{0}\\
  1 &: 2 &=&  0 &\mathrm{ marad }\ \ \mathbf{1}
\end{matrix}\ \right\uparrow

Gyors hatványozás[szerkesztés | forrásszöveg szerkesztése]

A kettes számrendszernek nagy jelentősége van a gyors hatványozásban. Egy nk 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 i-ik helyiértékén 1 van, akkor N:=N*d;
  3. ha i k legnagyobb helyiértékét jelölte, az algoritmus véget ért
  4. i:=i+1, d:=d*d
  5. ugrás 2-re

Források[szerkesztés | forrásszöveg szerkesztése]

Kapcsolódó szócikkek[szerkesztés | forrásszöveg szerkesztése]