Alapműveletek kettes számrendszerben

Példák algoritmusokra

Az tárgyalt algoritmusok leírását a legtöbb esetben rövid JavaScript programokkal is bemutatjuk. A példák kipróbálásához felhasználható online JavaScript interpreter:

Online JavaScript Interpreter by Peter Jipsen, Chapman University (January 2013).
http://math.chapman.edu/~jipsen/js/ (2020-11-19)

Megjegyzés: Ha a fenti link valamilyen oknál fogva nem működik, használjuk az alábbi linket.

A JavaScript programok folyamatábráját megjeleníthetjük az alábbi webes alkalmazás segítségével:

Live code editor. Created by Bogdan Lyashenko.
https://bogdan-lyashenko.github.io/js-code-to-svg-flowchart/docs/live-editor/index.html (2022-10-02)

A folyamatábra a 'for' ciklust nem megfelelően ábrázolja, ezért érdemes ezeket mindig átírni 'while' ciklusra, mielőtt megjelenítenénk a program folyamatábráját.

Alapműveletek kettes számrendszerben: összeadás

Mivel a kettes számrendszerben csak két számjegyünk van, az egy számjegyből álló kettes számrendszerbeli számok összeadásához az alábbi táblázatra van szükségünk:

b1 b2 s=b1+b2
0 0 1
0 1 1
1 0 1
1 1 10

A táblázatból látható, hogy 12+12=102 vagyis két 1-es összeadása két számjegyből álló bináris számot eredményez. Ezt úgy is megfogalmazhatjuk, hogy két 1-es összeadásakor az alacsonyabb helyiértékről ún. átvitel keletkezik a magasabb helyiértékre.

Mivel az azonos helyiértékű számjegyek összeadásakor az átvitelt is figyelembe kell vennünk, érdemes a fenti táblázatot bővíteni egy harmadik oszloppal, amelyben az összeadandó b1 és b2 bitek mellett az átvitelt jelentő "bemeneti" (ti. az előző helyiértékről átvett, cin) és "kimeneti" (ti. a következő helyiértékre átviendő, cout) bitek szerepelnek:

félösszeadó,⇒ ill. egybites teljes összeadó⇒
igazságtáblázata
b1 b2 cin s=b1+b2 cout
0 0 0 0 0
1 0 0 1 0
0 1 0 1 0
1 1 0 0 1
0 0 1 1 0
1 0 1 0 1
0 1 1 0 1
1 1 1 1 1

Lássunk ezek után néhány példát bináris számok összeadására.

Legyenek 'p', 'q' és 'r' 8 bites regiszterek, amelyekben a számokat direkt kódban⇒ ábrázoljuk.

Példa összeadásra:
Legyen p=0010|10112 és q=0011|10102; r=p+q=?2

r=p+q
p =  0 0 1 0 | 1 0 1 1
q =  0 0 1 1 | 1 0 1 0
átvitel 0 0 1 1 1 | 0 1 0
r =  0 1 1 0 | 0 1 0 1

Eredmény: r=0110|01012=10110

Ellenőrzés: p=4310, q=5810, r=10110, vagyis p+q=r teljesül, tehát jól számoltunk.

Ha direkt kódban ábrázolt bináris számok összeadásakor az utolsó (legmagasabb helyiértékű) biten átvitel keletkezik, akkor a két szám összege túl nagy lesz, ezért már nem ábrázolható az 'r' regiszterben. Ilyen esetekben túlcsordulásról beszélünk.

Próbáljuk ki a fenti algoritmust megvalósító JavaScript programot a JavaScript interpreter használatával. (Figyeljük meg a korábban megadott igazságtáblázat⇒ megvalósítását az egymásba ágyazott if-else szerkezetek használatával.) 

// bináris számok összeadása (8 biten)

function dec2bin(x,m) {
 var b="";
 var q=x;
 
 while(q>0) {
  if(q%2==1) {
   b="1"+b;
   q=q-1;
   }
  else {
   b="0"+b;
   }
  q=q/2;
  }
 while(b.length<m) {
  b="0"+b; // vezető 0
  }
 return b;
 }

function bin2dec(x) {
 var d=0;
 var i=0,h=1;
 for(i=1;i<x.length;i++) {
  h=h*2;
  }
 for(var i=0;i<x.length;i++) {
  if(x[i]=="1") {
   d=d+h;
   }
  h=h/2;
  }
 return d;
 }

/* feltétel: a két bináris szám 8 bites, tehát 0<=x1<=127 és 0<=x2<=127 teljesül */

var m=8; // bitek száma
var x1=114; // max. 255
var x2=87; // max. 255

writeln("Decimális összeadás: "+x1+"+"+x2+"="+(x1+x2));
writeln();
writeln("Bináris összeadás:");

var b1=dec2bin(x1,m);
var b2=dec2bin(x2,m);

var s1=x1.toString();
while(s1.length<3) {
 s1=" "+s1; // vezető szóköz
 }

var s2=x2.toString();
while(s2.length<3) {
 s2=" "+s2; // vezető szóköz
 }

writeln();
writeln("   x1 =   "+b1+" = "+s1);
writeln("   x2 =   "+b2+" = "+s2);

var y=""; // összeg
var t=""; // átvitelek sorozata ("atv")

var i=m-1; // legkisebb helyiérték indexe
/* a jobb szélső bit indexét i=x1.length-1; vagy i=x2.length-1; módon is megadhatjuk */
var a="0"; // átvitel
t="0";

while(i>=0) {
 if(a=="0") {
  if(b1[i]=="0" && b2[i]=="0") { y="0"+y; }
  else if(b1[i]=="0" && b2[i]=="1") { y="1"+y; }
  else if(b1[i]=="1" && b2[i]=="0") { y="1"+y; }
  else { 
   y="0"+y; 
   a="1";
   }
  }
 else {
  if(b1[i]=="0" && b2[i]=="0") { 
   y="1"+y; 
   a="0";
   }
  else if(b1[i]=="0" && b2[i]=="1") { y="0"+y; }
  else if(b1[i]=="1" && b2[i]=="0") { y="0"+y; }
  else { y="1"+y; }
  }
 t=a+t;
 i=i-1;
 }

var s3=bin2dec(y).toString();
while(s3.length<3) {
 s3=" "+s3; // vezető szóköz
 }

writeln("  atv =  "+t);
writeln("          --------------");
writeln("          "+y+" = "+s3);

writeln("__________");

Jegyezzük meg, hogy a kettes számrendszerbeli számok bitjeit logikai értékeknek tekintve a bináris számok összeadása logikai műveletek segítségével is kifejezhető.⇒ 

// bináris számok összeadása (8 biten) (2. változat)

function kon(x,y) {
 var a=Boolean(x), b=Boolean(y);
 var c=a && b;
 return Number(c);
 }

function dis(x,y) {
 var a=Boolean(x), b=Boolean(y);
 var c=a || b;
 return Number(c);
 }

function dxs(x,y) {
 var a=Boolean(x), b=Boolean(y);
 var c=(!a && b) || (a && !b);
 return Number(c);
 }

var m=8; // bitek száma
var x1="00101011"; // 8 bit
var x2="00111010"; // 8 bit

writeln("Bináris összeadás:");

writeln();
writeln("   x1 =   "+x1);
writeln("   x2 =   "+x2);

var y=""; // összeg
var t=""; // átvitelek sorozata ("atv")

var atv=0;
var v,w,u,a,b;
for(var i=m-1;i>=0;i--) {
 /* x1[i], x2[i] és atv összeadása */
 v=Number(x1[i]);
 w=Number(x2[i]);
 u=dxs(v,w); // részösszeg;
 a=kon(v,w);
 y=dxs(u,atv)+y;
 b=kon(u,atv);
 atv=dis(a,b); // átvitel
 t=atv+t;
 }

writeln("  atv =  "+t);
writeln("          --------");
writeln("          "+y);

writeln("__________");

Alapműveletek kettes számrendszerben: kivonás

Példa kivonásra:
Legyen p=0110|10112 és q=0011|01102; r=p−q=?2

r=p−q
p =  0 1 1 0 | 1 0 1 1
q =  0 0 1 1 | 0 1 1 0
átvitel 0 1 1 0 | 1 0 0 0
r =  0 0 1 1 | 0 1 0 1

Megjegyzés: az átvitel sorban szereplő biteket a felette levő sor (a 'q' kivonandó) bitjeihez kell hozzáadni.

Eredmény: r=0011|01012=5310

Ellenőrzés: p=10710, q=5410, r=5310, vagyis p−q=r teljesül, tehát jól számoltunk.

A kivonást egész számok esetén a negatív egész számok kettes komplemens kódban⇒ történő ábrázolásával összeadásra tudjuk visszavezetni.

Legyenek 'p', 'q' és 'r' ismét 8 bites regiszterek, amelyekben a számokat kettes komplemens kódban ábrázoljuk.

Példa:
Legyen p=1010|10112 és q=0001|10102; r=p+q=?2

p =  1 0 1 0 | 1 0 1 1
q =  0 0 0 1 | 1 0 1 0
átvitel 0 1 1 1 | 0 1 0 0
r =  1 1 0 0 | 0 1 0 1

Eredmény: r=1100|01012

Ellenőrzés:
• mivel 'p' negatív, |p|=0101|01002+12=0101|01012=8510 tehát p=−8510;
• q=0001|10102=2610;
• mivel 'r' is negatív, |r|=0011|10102+12=0011|10112=5910 tehát r=−5910.

Mivel p=−8510, q=2610, r=−5910, ezért p+q=r teljesül, tehát jól számoltunk. Az elvégzett összeadás egyenértékű a 2610−8510=−5910 kivonással, amit a példában a negatív számokat kettes komplemens kódban ábrázolva összeadásra vezettünk vissza.

A kivonás megvalósításához szükségünk van két további függvényre, amelyek a negatív bináris számok átalakítását végzik el egyes, ill. kettes komplemens kódra. 

function dec2bin(x,m) {
 var b="";
 var q=x;
 while(q>0) {
  if(q%2==1) {
   b="1"+b;
   q=q-1;
   }
  else {
   b="0"+b;
   }
  q=q/2;
  }
 while(b.length<m) {
  b="0"+b; // vezető 0
  }
 return b;
 }

function bin2dec(x) {
 var d=0;
 var i=0,h=1;
 for(i=1;i<x.length;i++) {
  h=h*2;
  }
 for(var i=0;i<x.length;i++) {
  if(x[i]=="1") {
   d=d+h;
   }
  h=h/2;
  }
 return d;
 }

function comp1(x) {
 var t="";
 for(i=0;i<x.length;i++) {
  if(x[i]=="1") {
   t=t+"0";
   }
  else {
   t=t+"1";
   }
  }
 return t;
 }

function comp2(x) {
/* binárisan '1' hozzáadása x-hez */
 var t="";
 var c="1";
 for(k=x.length-1;k>=0;k--) {
  if(c=="1") {
   if(x[k]=="0") {
    t="1"+t;
    c="0";
    }
   else { // x[k]=="1"
    t="0"+t;
    }
   }
  else { // c=="0"
   /* innentől átmásoljuk x karaktereit */
   t=x[k]+t;
   }
  }
 if(c=="1") {
  /* túlcsordulás */
  t=c+t;
  }
 return t;
 }

var m=8; // ennyi biten ábrázoljuk a bináris számokat
var d=-9; // -128<=d<0 (2^7=128, 7=m-1)
writeln("Negatív decimális szám: "+d);

d=Math.abs(d);
var x=dec2bin(d,m);
writeln("Bináris alak: "+x);

var t=comp1(x);
writeln("Egyes komplemens: "+t);

t=comp2(t);
writeln("Kettes komplemens: "+t);

writeln("----------");

writeln("Kettes komplemens: "+t);

t=comp1(t);
writeln("Egyes komplemens: "+t);

x=comp2(t);
writeln("Bináris alak: "+x);

d=-bin2dec(x);
writeln("Negatív decimális szám: "+d);

writeln("__________");

A fenti függvények, valamint a bináris összeadást végző program alapján már el nem nehéz elkészíteni a bináris kivonást megvalósító programot. 

// bináris számok összeadása (8 biten)

function dec2bin(x,m) {
 var b="";
 var q=x;
 while(q>0) {
  if(q%2==1) {
   b="1"+b;
   q=q-1;
   }
  else {
   b="0"+b;
   }
  q=q/2;
  }
 while(b.length<m) {
  b="0"+b; // vezető 0
  }
 return b;
 }

function bin2dec(x) {
 var d=0;
 var i=0,h=1;
 for(i=1;i<x.length;i++) {
  h=h*2;
  }
 for(var i=0;i<x.length;i++) {
  if(x[i]=="1") {
   d=d+h;
   }
  h=h/2;
  }
 return d;
 }

function comp1(x) {
 var t="";
 for(i=0;i<x.length;i++) {
  if(x[i]=="1") {
   t=t+"0";
   }
  else {
   t=t+"1";
   }
  }
 return t;
 }

function comp2(x) {
/* binárisan '1' hozzáadása x-hez */
 var t="";
 var c="1";
 for(k=x.length-1;k>=0;k--) {
  if(c=="1") {
   if(x[k]=="0") {
    t="1"+t;
    c="0";
    }
   else { // x[k]=="1"
    t="0"+t;
    }
   }
  else { // c=="0"
   /* innentől átmásoljuk x karaktereit */
   t=x[k]+t;
   }
  }
 if(c=="1") {
  /* túlcsordulás */
  t=c+t;
  }
 return t;
 }

var m=8; // bitek száma
var x1=14; // kisebbítendő; 0<=x1<127
var x2=27; // kivonandó; 0<x2<=128

writeln("Decimális kivonás: "+x1+"-"+x2+
        "="+(x1-x2));
writeln();
writeln("Bináris kivonás:");

var b1=dec2bin(x1,m);
var b2=dec2bin(x2,m);
b2=comp1(b2);
b2=comp2(b2);

var s1=x1.toString();
while(s1.length<4) {
 s1=" "+s1; // vezető szóköz
 }

var s2=x2.toString();
s2="-"+s2;
while(s2.length<4) {
 s2=" "+s2; // vezető szóköz
 }

writeln();
writeln("   x1 =   "+b1+" = "+s1);
writeln("   x2 =   "+b2+" = "+s2);

var y=""; // összeg
var t=""; // átvitelek sorozata ("atv")

var a="0"; // átvitel
t="0";

for(var i=m-1;i>=0;i--) {
 if(a=="0") {
  if(b1[i]=="0" && b2[i]=="0") { y="0"+y; }
  else if(b1[i]=="0" && b2[i]=="1") { y="1"+y; }
  else if(b1[i]=="1" && b2[i]=="0") { y="1"+y; }
  else { 
   y="0"+y; 
   a="1";
   }
  }
 else {
  if(b1[i]=="0" && b2[i]=="0") { 
   y="1"+y; 
   a="0";
   }
  else if(b1[i]=="0" && b2[i]=="1") { y="0"+y; }
  else if(b1[i]=="1" && b2[i]=="0") { y="0"+y; }
  else { y="1"+y; }
  }
 t=a+t;
 }

var s3;
if(y[0]=="1") { // előjelbit!
 y=comp1(y);
 y=comp2(y);
 s3="-"+bin2dec(y).toString();
 }
else {
 s3=bin2dec(y).toString();
 }

while(s3.length<4) {
 s3=" "+s3; // vezető szóköz
 }

writeln("          --------------");
writeln("          "+y+" = "+s3);

writeln("__________");

Alapműveletek kettes számrendszerben: szorzás

Direkt kódban ábrázolt kettes számrendszerbeli számok esetén a tizes számrendszerben jól ismert szorzási algoritmust alkalmazhatjuk. Jegyezzük meg a következőket:

Legyenek 'p', 'q' és 'r' 8 bites regiszterek, amelyekben a számokat direkt kódban ábrázoljuk.

Példa szorzásra:
Legyen p=0000|10112 és q=0000|10102; r=p*q=?2

p*q =  0 0 0 0 1 0 1 1 * 00001010
+ 0 0 0 0 1 0 1 1
0 0 0 0 0 0 0 0
0 0 0 0 1 0 1 1
0 0 0 0 0 0 0 0
r =  0 0 0 0 1 1 0 1 1 1 0

Ha a szorzó kettőnél több 1-est tartalmaz akkor a táblázatban kettőnél több kettes számrendszerbeli számot kell összeadnunk. Ilyenkor a táblázatba több segédsort is beírhatunk, amelyek az egyes részösszegeket (és szükség esetén az ezekhez tartozó átviteleket) tartalmazzák.

Eredmény: r=0110|11102=11010

Ellenőrzés: p=1110, q=1010, r=11010, vagyis p*q=r teljesül, tehát jól számoltunk.

Ha a szorzat túl nagy, és ezért már nem ábrázolható a 8 bites 'r' regiszterben, túlcsordulásról beszélünk.

A szorzás megvalósításához szükségünk van néhány hasznos függvényre. 

function trim0(x) {
 var t="", i=0, b=0;
 while(i<x.length) {
  if(x[i]=="1") {
   b=1;
   }
  if(b==1) {
   t=t+x[i];
   }
  i=i+1;
  }
 return t;
 }

function mult2(x,m) {
 var t=x, i=0;
 while(i<m) {
  t=t+"0"; // eltolás balra 1 bittel
  i=i+1;
  }
 return t;
 }

var x="001001";
writeln("Bináris egész szám: "+x);

var t=trim0(x);
writeln("-- vezető 0-k levágása: "+t);

var m=3;
var t=mult2(t,m);
writeln("-- bináris szám eltolása "+m+
        " bittel balra: "+t);

writeln("__________");

A bináris szorzást megvalósító program: 

function trim0(x) {
 var t="", i=0, b=0;
 while(i<x.length) {
  if(x[i]=="1") {
   b=1;
   }
  if(b==1) {
   t=t+x[i];
   }
  i=i+1;
  }
 return t;
 }

function mult2(x,m) {
 var t=x, i=0;
 while(i<m) {
  t=t+"0"; // eltolás balra 1 bittel
  i=i+1;
  }
 return t;
 }

function plus(x,y) {
 /* ez most nem bináris összeadás, így rövidebb :-) */
 var t=parseInt(x,2)+parseInt(y,2);
 return t.toString(2);
 }

var p="00001011", q="00001010";
var p1=trim0(p); 
var p0="";
var q1=trim0(q);

var s1="", s2="";
for(var i=0;i<p1.length;i++) {
 p0+="0";
 s1+="-";
 }
for(var i=0;i<p1.length+q1.length-1;i++) {
 s2+="-";
 }

writeln("Az összeszorzandó számok: "+p+"*"+q);

writeln("\n "+p1+"*"+q1);
writeln(" "+s1);

tag=new Array();
szorzat="0";

var j=q1.length-1;
s="";
for(var i=0;i<q1.length;i++) {
 if(q1[i]=="1") {
  tag[i]=mult2(p1,j);
  }
 else {
  tag[i]=mult2(p0,j);
  }
 writeln(" "+s+tag[i]);
 szorzat=plus(szorzat,tag[i]);
 s+=" ";
 j--;
 }
writeln(" "+s2);

if(szorzat.length<p1.length+q1.length) {
 // nincs túlcsordulás :-)
 szorzat=" "+szorzat;
 }
writeln(szorzat);

writeln("__________");

Alapműveletek kettes számrendszerben: osztás

Direkt kódban ábrázolt kettes számrendszerbeli számok esetén a tizes számrendszerben jól ismert osztási algoritmust alkalmazhatjuk.

Mivel a hányados csak 0 és 1 számjegyekből áll, az egyes osztási lépésekben a maradékokból kivonandó részletszorzatok vagy csupa zérusból állnak, vagy magából az osztóból.

Legyenek 'p', 'q' és 'r' 8 bites regiszterek, amelyekben a számokat direkt kódban ábrázoljuk.

Példa osztásra:
Legyen p=1100|10112 és q=0000|10102; r=p/q=?2

p/q =  1 1 0 0 1 0 1 1 : 1 0 1 0 = 1 0 1 0 0
1 1 0 0 0 0 0 0 0 0
− 1 0 1 0
0 0 1 0 1
− 0 0 0 0
0 1 0 1 0
− 1 0 1 0
0 0 0 0 1
− 0 0 0 0
0 0 0 1 1
− 0 0 0 0
d =  0 0 1 1

Ha az osztó (q) nincs meg maradék nélkül az osztandóban (p), akkor maradék képződik (d), amit a táblázat utolsó sora mutat. Ilyenkor maradékos osztást hajtottunk végre.

Eredmény:
    az osztó: r=0001|01002=2010
    a maradék: d=0000|00112=310

Ellenőrzés: p=20310, q=1010, r=2010, d=310, vagyis p=q*r+d teljesül, tehát jól számoltunk.

→ Tartalom
Boda István, 2023-24.