Kettes számrendszer

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

Ez a szócikk a számrendszerről szól. Hasonló címmel lásd még: Bináris prefixum.

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é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.

Tartalomjegyzék 1 Története 2 Átváltása 3 Gyors hatványozás 4 Lásd még

[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.

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

[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 (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

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₂(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.

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

[szerkesztés] Lásd még

• Számrendszerek az informatikában
• Tizenhatos számrendszer
• Nyolcas számrendszer
• Ötös számrendszer
• Tízes számrendszer
• Hármas számrendszer
• Négyes számrendszer