Informatika alapjai

Példák algoritmusokra:
4.1. bináris szám átalakítása hexadecimális számmá^⇒

1. egész szám átváltása
Példa: 1010|1101₂ = ?₁₆
Két fontos dolgot tudnunk kell az algoritmus megértéséhez:
(1) Mivel a kettes számrendszerbeli (egész) számok rendszerint elég sok számjegyből állnak, érdemes a bináris számjegyeket jobbról négyes csoportokra osztani (az utolsó csoportot pedig balról kiegészíteni "vezető" nullákkal).
Például ha a 1010010110 bináris szám számjegyeit jobbról négyes csoportokra bontjuk, akkor
    0010|1001|0110
adódik.

(2) A hexadecimális számok számjegyei a decimális számjegyek (0, 1, ..., 9) mellett az A, B, C, D, E és F számjegyeket is magukba foglalják.

A bináris egész számokat hexadecimális számokká alakító algoritmus lépései:

az átváltandó kettes számrendszerbeli egész szám számjegyeit (pl. 1010|1101) jobbról négyes csoportokra osztjuk fel; a példa esetén ekkor

jobbról az első csoport 1101
jobbról a második csoport 1010

a kapott négy bináris számjegyből álló csoportokat tetszőleges sorrendben, például balról jobbra haladva egyenként tízes számrendszerbeli számokká alakítjuk (alkalmazva a korábban megismert 2. algoritmust^⇒)

1010₂=8+2=10₁₀
1101₂=8+4+1=13₁₀

az egyes csoportoknak megfelelő tízes számrendszerbeli számokat tizenhatos számrendszerbeli (hexadecimális) számjegyekké alakítjuk

1010₂=8+2=10₁₀=A₁₆
1101₂=8+4+1=13₁₀=D₁₆

a kapott tizenhatos számrendszerbeli számjegyeket egymás után felírva megkapjuk a keresett hexadecimális számot

Eredmény: 1010|1101₂ = AD₁₆

A fenti példa táblázatos formában:
1010|1101₂ = ?₁₆

bin
számjegy helyi érték szorzat hexa
számjegy
1 2³=8 8
0 2²=4 0
1 2¹=2 2
0 2⁰=1 0
összesen 10 A

1 2³=8 8
1 2²=4 4
0 2¹=2 0
1 2⁰=1 1
összesen 13 D

Eredmény:
1010|1101₂ = AD₁₆
Ellenőrzés:
    (1) 1010|1101₂ = 1*2⁷ + 0*2⁶ + 1*2⁵ + 0*2⁴ + 1*2³ + 1*2² + 0*2¹ + 1*2⁰ = 128 + 32 + 8 + 4 + 1 = 173₁₀ (ld. 2. algoritmus^⇒)
    (2) AD₁₆ = 10*16¹ + 13*16⁰ = 10*16 + 13*1 = 160 + 13 = 173₁₀ (ld. 3. algoritmus^⇒)
A két szám megegyezik (ok).

A fenti algoritmust megvalósító JavaScript program:
// bináris szám átalakítása hexadecimális számmá 

function dec2hex(sz) {
 var hx="-1";
 switch(sz) {
  case 10: hx="A"; break;
  case 11: hx="B"; break;
  case 12: hx="C"; break;
  case 13: hx="D"; break;
  case 14: hx="E"; break;
  case 15: hx="F"; break;
  default: 
   hx=""+sz;  
  }
 return hx;
 }

var x="10101101";
while(x.length%4!=0) {
 x="0"+x; // vezető 0-k beírása
 }

var k=x.length-1;
var t=""; // végeredmény

var s="";
var h=0;
var helyiertek=1;

for(var i=0;i<x.length;i++) {
 s=x[k]+s;
 if(x[k]=="1") {
  h+=helyiertek;
  }
 helyiertek*=2;
 k--;
 if(i%4==3) {
  writeln("    "+s+" = "+h+" = "+dec2hex(h));
  t=dec2hex(h)+t;
  s="";
  h=0;
  helyiertek=1;
  }
 }

writeln();
writeln(x+" = "+t);

writeln("____________"); 

bin számjegy	helyi érték	szorzat	hexa számjegy
1	2³=8	8
0	2²=4	0
1	2¹=2	2
0	2⁰=1	0
	összesen	10	A

1	2³=8	8
1	2²=4	4
0	2¹=2	0
1	2⁰=1	1
	összesen	13	D

Példák algoritmusokra:
4.2. hexadecimális szám átalakítása bináris számmá

A fordított irányú átváltás, azaz egy hexadecimális szám átváltása bináris számmá az előző algoritmushoz teljesen hasonlóan működik. Vegyünk egy tetszőleges hexadecimális számot, és

alakítsuk át a hexadecimális számjegyeket egyenként (pl. balról jobbra haladva) négy számjegyből álló (4 bites) bináris számokká;

ha szükséges, tegyünk be vezető nullákat, hogy a kapott bitsorozatok mindig 4 bitből álljanak

balról jobbra haladva "olvassuk össze" a kapott négy bites bitsorozatokat (szükség esetén a bitsorozatok közé betehetünk elválasztó karaktereket (pl. függőleges vonalat vagy szóközt) a könnyebb olvashatóság kedvéért)

Példa: 2AD₁₆ = ?₂

2₁₆ = 0010₂
A₁₆ = 1010₂
D₁₆ = 1101₂

Tehát az eredmény: 2AD₁₆ = 0010|1010|1101₂

Az algoritmust megvalósító JavaScript program:
// hexadecimális szám átalakítása bináris számmá 

function hex2dec(hx) {
 var sz=-1;
 switch(hx) {
  case "a":
  case "A": sz=10; break;
  case "b":
  case "B": sz=11; break;
  case "c":
  case "C": sz=12; break;
  case "d":
  case "D": sz=13; break;
  case "e":
  case "E": sz=14; break;
  case "f":
  case "F": sz=15; break;
  default: 
   sz=parseInt(hx);  
  }
 return sz;
 }

var x="2AD";

writeln("A hexadecimális szám: "+x);
writeln();

var t=""; // végeredmény

for(var i=0;i<x.length;i++) {
 var h=hex2dec(x[i]);
 var helyiertek=8;
 var s=""; // részeredmény

 while(helyiertek>=1) {
  if(h>=helyiertek) {
   s=s+"1";
   h-=helyiertek;
   }
  else {
   s=s+"0";
   }
  helyiertek/=2;
  }

 writeln("    "+x[i]+" = "+hex2dec(x[i])+" = "+s);
 if(i>0) {
  t=t+" ";
  }
 t=t+s;
 }

writeln();
writeln(x+" bináris alakja: "+t);

writeln("____________"); 

Példák algoritmusokra:
4.3. bináris törtszámok és hexadecimális törtszámok átalakítása

A bináris és hexadecimális számrendszerben ábrázolt egész számok átváltására korábban megismert algoritmusok teljesen hasonlóan működnek törtszámok esetén is.
1. példa: 0.1011|0101₂ = ?₁₆
Mivel a kettes számrendszerbeli (tört) számok rendszerint elég sok számjegyből állnak, érdemes a bináris számjegyeket balról (0. után kezdődően) négyes csoportokra osztani (az utolsó csoportot pedig jobbról kiegészíteni "vezető" nullákkal).
Például ha a 0.10110101 bináris szám számjegyeit balról négyes csoportokra bontjuk, akkor
    0.1011|0101
adódik.

A bináris törtszámokat hexadecimális törtszámokká alakító algoritmus lépései:

az átváltandó kettes számrendszerbeli egész szám számjegyeit (pl. 0.1011|0101) balról négyes csoportokra osztjuk fel; a példa esetén ekkor

balról az első csoport 1011
balról a második csoport 0101

a kapott négy bináris számjegyből álló csoportokat balról jobbra haladva egyenként tízes számrendszerbeli számokká alakítjuk (alkalmazva a korábban megismert 2. algoritmust^⇒)

1011₂=8+2+1=11₁₀
0101₂=4+1=5₁₀

az egyes csoportoknak megfelelő tízes számrendszerbeli számokat tizenhatos számrendszerbeli (hexadecimális) számjegyekké alakítjuk

1011₂=8+2+1=11₁₀=B₁₆
0101₂=4+1=5₁₀=5₁₆

a kapott tizenhatos számrendszerbeli számjegyeket egymás után felírva megkapjuk a keresett hexadecimális számot

Eredmény: 0.1011|0101₂ = 0.B5₁₆

A fenti példa táblázatos formában:
0.1011|0101₂ = ?₁₆

bin
számjegy helyi érték szorzat hexa
számjegy
1 2³=8 8
0 2²=4 0
1 2¹=2 2
1 2⁰=1 1
összesen 11 B

0 2³=8 0
1 2²=4 4
0 2¹=2 0
1 2⁰=1 1
összesen 5 5

Eredmény:
0.1011|0101₂ = 0.B5₁₆
Ellenőrzés:
    (1) 0.1011|0101₂ = 1*2⁻¹ + 1*2⁻³ + 1*2⁻⁴ + 1*2⁻⁶ + 1*2⁻⁸ = 1/2 + 1/8 + 1/16 + 1/64 + 1/256 = 128/256 + 32/256 + 16/256 + 4/256 + 1/256 = 181/256 = 0.70703125₁₀
    (2) 0.B5₁₆ = 11*16⁻¹ + 5*16⁻² = 11/16 + 5/256 = 176/256 + 5/256 = 181/256 = 0.70703125₁₀
A két szám megegyezik (ok).

2. példa: 0.B5₁₆ = ?₂
A hexadecimális törtszámokat bináris törtszámokká úgy alakítjuk át, hogy minden hexadecimális számjegyet négyjegyű bináris számmá alakítunk:
    B₁₆=1011₂
    5₁₆=0101₂
Eredmény:
0.B5₁₆ = 0.1011|0101₂
Ellenőrzés:
    (1) 0.B5₁₆ = 11*16⁻¹ + 5*16⁻² = 11/16 + 5/256 = 176/256 + 5/256 = 181/256 = 0.70703125₁₀
    (2) 0.1011|0101₂ = 1*2⁻¹ + 1*2⁻³ + 1*2⁻⁴ + 1*2⁻⁶ + 1*2⁻⁸ = 1/2 + 1/8 + 1/16 + 1/64 + 1/256 = 128/256 + 32/256 + 16/256 + 4/256 + 1/256 = 181/256 = 0.70703125₁₀
A két szám megegyezik (ok).
A fenti algoritmust megvalósító JavaScript program:
// bináris tört átalakítása hexadecimális törtté

var hex="0123456789ABCDEF";

var x0="0.0111001"; // eredeti tört
var x=x0.substring(2);
while(x.length%4!=0) {
 x=x+"0"; // closing 0
 }

var t=""; // végeredmény törtrésze

var s=""; // négy bites csoport
var h=0; // négy bites csoport decimális értéke
var p=8; // kezdő helyiérték

for(var i=0;i<x.length;i++) {
 s=s+x[i];
 if(x[i]==1) {
  h+=p;
  }
 p/=2;
 if(i%4==3) {
  writeln("    "+s+" = "+h+" = "+hex[h]);
  t=t+hex[h];
  s="";
  h=0;
  p=8;
  }
 }

writeln();
writeln(x0+" = 0."+t);

writeln("____________"); 

bin számjegy	helyi érték	szorzat	hexa számjegy
1	2³=8	8
0	2²=4	0
1	2¹=2	2
1	2⁰=1	1
	összesen	11	B

0	2³=8	0
1	2²=4	4
0	2¹=2	0
1	2⁰=1	1
	összesen	5	5

Példák algoritmusokra:
5. decimális szám átalakítása hexadecimális számmá^⇒

Egy decimális számot a legegyszerűbben úgy alakíthatunk át hexadecimális számmá, hogy a decimális számot először bináris számmá alakítjuk, majd utána a kapott bináris számot átváltjuk hexadecimális számmá.
Példa: 314₁₀ = ?₁₆

1. lépés: az átváltandó tízes számrendszerbeli számot kettes számrendszerbeli (bináris) számmá alakítjuk (ld. 3. algoritmus^⇒)
2. lépés: az így kapott bináris számot tizenhatos számrendszerbeli (hexadecimális) számmá alakítjuk (ld. 4. algoritmus^⇒)

1. lépés

hányados maradék
314
314:2= 157 0
157:2= 78 1
78:2= 39 0
39:2= 19 1

19:2= 9 1
9:2= 4 1
4:2= 2 0
2:2= 1 0

1:2= 0 1

Tehát 314₁₀ = 1|0011|1010₂ → 0001|0011|1010₂
2. lépés

bin
számjegy helyi érték szorzat hexa
számjegy
0 2³=8 0
0 2²=4 0
0 2¹=2 0
1 2⁰=1 1
összesen 1 1

0 2³=8 0
0 2²=4 0
1 2¹=2 2
1 2⁰=1 1
összesen 3 3

1 2³=8 8
0 2²=4 0
1 2¹=2 2
0 2⁰=1 0
összesen 10 A

Tehát 1|0011|1010₂ = 13A₁₆
Eredmény:
314₁₀ = 13A₁₆
Ellenőrzés:
13A₁₆ = 1*16² + 3*16¹ + 10*16⁰ = 1*16*16 + 3*16 + 10*1 = 256 + 48 + 10 = 314₁₀ (ok)

Egy decimális számot a következő algoritmussal egy lépésben is átalakíthatunk hexadecimális számmá:

az átváltandó tízes számrendszerbeli számot (pl. 314) addig osztjuk 16-tal, amíg a hányados 0 nem lesz
minden lépésben felírjuk az osztás maradékát (amely egy 0 és 15=F közötti szám lesz)
az átváltandó szám hexadecimális számrendszerbeli alakját úgy kapjuk meg, hogy az osztások maradékait fordított sorrendben felírjuk

hányados maradék ellenőrzés
314
314:16= 19 10=A 314=16*19+10
19:16= 1 3 19=16*1+3
1:16= 0 1 1=16*0+1

Eredmény:
314₁₀ = 13A₁₆

A fenti algoritmust megvalósító JavaScript program:
// decimális szám átalakítása hexadecimális számmá osztással

function hex2dec(hx) {
 var sz=-1;
 switch(hx) {
  case "a":
  case "A": sz=10; break;
  case "b":
  case "B": sz=11; break;
  case "c":
  case "C": sz=12; break;
  case "d":
  case "D": sz=13; break;
  case "e":
  case "E": sz=14; break;
  case "f":
  case "F": sz=15; break;
  default: 
   sz=parseInt(hx);  
  }
 return sz;
 }

function dec2hex(sz) {
 var hx="-1";
 switch(sz) {
  case 10: hx="A"; break;
  case 11: hx="B"; break;
  case 12: hx="C"; break;
  case 13: hx="D"; break;
  case 14: hx="E"; break;
  case 15: hx="F"; break;
  default: 
   hx=""+sz;  
  }
 return hx;
 }

var x="314"; 

writeln("Decimális szám: "+x);
writeln();

var h="";
var q=x;

while(q>0) {
 write(q+" = ");
 var m=q%16;
 h=dec2hex(m)+h;
 q=q-m;
 q=q/16;
 writeln("16*"+q+" + "+m); 
 }

writeln();
writeln("Hexadecimális szám: "+h);

writeln("__________");
Egy további lehetőség egy decimális szám hexadecimális számmá alakítására a következő:

megkeressük 16-nak azt a legmagasabb hatványát, amely az átváltandó számnál kisebb vagy egyenlő;
a talált hatványt annyiszor vonjuk ki az átváltandó számból, amíg a különbség a hatványnál kisebb nem lesz;

a talált hatványhoz mint helyi értékhez tartozó számjegy a kivonások számával egyezik meg (értelemszerűen 9-nél nagyobb számjegynél a hexadecimális számjegyeket kell használnunk);

a kivonás maradékára addig ismételjük az eljárást, ameddig a kivonás eredménye 16-nál kisebb nem lesz;

az egyesek számát a kivonás eredménye adja;

az átváltandó szám hexadecimális számrendszerbeli alakjában azok a számjegyek, amelyekhez nem rendeltünk (zérusnál nagyobb) számjegyet, '0' értékűek lesznek.

Példa: 1526₁₀ = ?₂

hatvány átváltandó szám/maradék kivonások száma
1526
16²=256 1526−256=1270>256 1
1270−256=1014>256 2
1014−256=758>256 3
758−256=502>256 4
502−256=246<256 5

16¹=16 246−16=230>16 1
230−16=214>16 2
214−16=198>16 3
198−16=182>16 4
182−16=166>16 5
166−16=150>16 6
150−16=134>16 7
134−16=118>16 8
118−16=102>16 9
102−16=86>16 10
86−16=70>16 11
70−16=54>16 12
54−16=38>16 13
38−16=22>16 14
22−16=6<16 15=F

16⁰=1 6−1=5>1 1
5−1=4>1 2
4−1=3>1 3
3−1=2>1 4
2−1=1≥1 5
1−1=0<1 6

Eredmény:
5F6₁₆ = 5*16² + F*16¹ + 6*16⁰ = 5*256 + 15*16 + 6 = 1526₁₀

A fenti algoritmust megvalósító JavaScript program:
// decimális szám átalakítása hexadecimális számmá kivonásokkal

function hex2dec(hx) {
 var sz=-1;
 switch(hx) {
  case "a":
  case "A": sz=10; break;
  case "b":
  case "B": sz=11; break;
  case "c":
  case "C": sz=12; break;
  case "d":
  case "D": sz=13; break;
  case "e":
  case "E": sz=14; break;
  case "f":
  case "F": sz=15; break;
  default: 
   sz=parseInt(hx);  
  }
 return sz;
 }

function dec2hex(sz) {
 var hx="-1";
 switch(sz) {
  case 10: hx="A"; break;
  case 11: hx="B"; break;
  case 12: hx="C"; break;
  case 13: hx="D"; break;
  case 14: hx="E"; break;
  case 15: hx="F"; break;
  default: 
   hx=""+sz;  
  }
 return hx;
 }

var x=1526; 

writeln("Decimális szám: "+x);
writeln();

var h="";
var helyiertek=1;

while(16*helyiertek<=x) {
 helyiertek*=16;
 }

while(helyiertek>=1) {
 if(helyiertek<=x) {
  var sz=0;
  while(helyiertek<=x) {
   sz++;
   x-=helyiertek;
   }
  h+=dec2hex(sz);
  writeln("   Számjegy:    "+dec2hex(sz));
  writeln("   Helyi érték: "+helyiertek);
  }
 else {
  h+="0";
  writeln("   Számjegy:    "+0);
  writeln("   Helyi érték: "+helyiertek);
  }
 helyiertek/=16;
 }

writeln();
writeln("Hexadecimális szám: "+h);

writeln("__________");

	hányados	maradék
	314
314:2=	157	0
157:2=	78	1
78:2=	39	0
39:2=	19	1

19:2=	9	1
9:2=	4	1
4:2=	2	0
2:2=	1	0

1:2=	0	1

	hányados	maradék	ellenőrzés
	314
314:16=	19	10=A	314=16*19+10
19:16=	1	3	19=16*1+3
1:16=	0	1	1=16*0+1

hatvány	átváltandó szám/maradék	kivonások száma
	1526
16²=256	1526−256=1270>256	1
	1270−256=1014>256	2
	1014−256=758>256	3
	758−256=502>256	4
	502−256=246<256	5

16¹=16	246−16=230>16	1
	230−16=214>16	2
	214−16=198>16	3
	198−16=182>16	4
	182−16=166>16	5
	166−16=150>16	6
	150−16=134>16	7
	134−16=118>16	8
	118−16=102>16	9
	102−16=86>16	10
	86−16=70>16	11
	70−16=54>16	12
	54−16=38>16	13
	38−16=22>16	14
	22−16=6<16	15=F

16⁰=1	6−1=5>1	1
	5−1=4>1	2
	4−1=3>1	3
	3−1=2>1	4
	2−1=1≥1	5
	1−1=0<1	6

Számrendszerek, algoritmusok