Kettes számrendszer
A Wikipédiából, a szabad lexikonból.
A kettes vagy bináris számrendszer két számjegy, a 0 és az 1 segítségével ábrázolja a számokat. 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épek szinte kivétel nélkül ezt használják.
Tartalomjegyzék |
[szerkesztés] Története
A kettes számrendszer pontos leírását először Gottfried Leibniz adta meg a 17. században, 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.
[szerkesztés] Átváltása
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
Egy N szám kettes számrendszerben ábrázolt értékét a következő algoritmussal kaphatjuk meg:
- Megkeressük azt a d legnagyobb kettő-hatványt, ami nem nagyobb, mint N (ez éppen
lesz). - 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.
- Ha d=1, akkor az algoritmus véget ért.
- d:=d/2
- Ugrás 2-re.
[szerkesztés] Gyors hatványozás
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:
- N:=1, d:=n, i:=0
- ha k i-ik helyiértékén 1 van, akkor N:=N*d;
- ha i k legnagyobb helyiértékét jelölte, az algoritmus véget ért
- i:=i+1, d:=d*d
- ugrás 2-re


Based on work by