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:

  1. Megkeressük azt a d legnagyobb kettő-hatványt, ami nem nagyobb, mint N (ez éppen \big[\log_2(N)\big] 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 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

[szerkesztés] Lásd még