Algorithms related to number systems and data representation

List of the algorithms described below:

Below we deal with the following algorithms:

  1. converting a binary number to a decimal number⇒
  2. converting a hexadecimal number to a decimal number⇒
  3. converting a decimal number to a binary number
    • conversion of an integer⇒
      • converting a decimal number to a hexadecimal number
    • conversion of a fraction⇒
      • converting an infinite sequential fraction to a rational fraction⇒
      • computing the greatest common divisor of integers⇒
      • performing prime factorization⇒
  4. conversion between the binary and the hexadecimal number system⇒
    • converting a binary number to a hexadecimal number⇒
    • converting a hexadecimal number to a binary number⇒
  5. converting a decimal number to a hexadecimal number⇒
  6. basic arithmetic operations in the binary number system⇒

In most cases, the description of the discussed algorithms is also presented with short JavaScript programs. An online JavaScript interpreter that can be used to try the examples can be accessed as follows:

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

Important note: Since the link above doesn't work for some reason, let's use the link below.

The flowchart of the JavaScript programs can be displayed using the following web application:

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)

The flowchart does not represent the 'for' loop correctly, so it is always worth rewriting each 'for' loop into a 'while' loop before displaying the program's flowchart.

Examples of algorithms:
1. converting a binary number to a decimal number

Example: 11012 = ?10

digit positional value product
1 23=8 8
1 22=4 4
0 21=2 0
1 20=1 1
Total 13

Result:
11012 = 1310

Check:
1310 = 8 + 4 + 1 = 1*23 + 1*22 + 0*21 + 1*20 = 11012 (ok)

The JavaScript program implementing the above algorithm is as follows: 

// converting a binary number to a decimal number 

var x="1101"; 

writeln("Binary number: "+x);
writeln();

var d=0;
var posvalue=1;

for(var i=1;i<x.length;i++) {
 posvalue*=2;
 }

for(var i=0;i<x.length;i++) {
 var sz;
 if(x[i]=="1") {
  sz=1;
  }
 else {
  sz=0;
  }
 writeln("   Digit           : "+sz);
 writeln("   Positional value: "+posvalue);
 var r=sz*posvalue;
 writeln("      Partial sum: "+r);
 d+=r;
 posvalue/=2;
 }

writeln();

writeln("Decimal number: "+d);

writeln("__________");

Similar to binary integers, we can convert binary fractional numbers into decimal fractions. The only difference is that the positional values of fractional numbers will be the powers of 2 raised to negative integers (starting from the positional value 2−1=1/2).

It is enough to deal only with numbers that are positive and less than 1 (i.e. their whole part is zero), since the whole part and the fractional part of a binary number can be converted separately into a decimal number.

Example: 0.11012 = ?10

digit positional value product
1 2−1=1/2 1/2
1 2−2=1/4 1/4
0 2−3=1/8 0
1 2−4=1/16 1/16
Sum of all products 13/16

Result:
0.11012 = 13/1610 = 0.812510

Check:
0.812510 = 0.5 + 0.25 + 0.0625 = 1*2−1 + 1*2−2 + 0*2−3 + 1*2−4 = 0.11012 (ok)

The JavaScript program implementing the above algorithm is as follows: 

// converting binary fractions to decimal fractions 

/* condition: the binary fractional number is positive and less than 1 (i.e. 0<x<1) */

var x="0.1101"; 

writeln("Binary fraction: "+x);
writeln();

var d=0;
var h=1/2;

for(var i=2;i<x.length;i++) {
 var sz;
 if(x[i]=="1") {
  sz=1;
  }
 else {
  sz=0;
  }
 writeln("   Digit   : "+sz);
 writeln("   Positional value: "+h);
 var r=sz*h;
 writeln("      Partial sum: "+r);
 d+=r;
 h/=2;
 }

writeln();

writeln("Decimal fraction: "+d);

writeln("__________");

Examples of algorithms:
2. converting a hexadecimal number to a decimal number

Example: 24C16 = ?10

digit positional value product
2 162=256 512
4 161=16 64
C 160=1 12
Total 588

Result:
24C16 = 58810

Check:
58810 = 512 + 64 + 12 = 2*256 + 4*16 + 12* 1 = 2*162 + 4*161 + 12*160 = 24C16 (ok)

The JavaScript program implementing the above algorithm is as follows: 

// converting a hexadecimal number to a decimal number 

// var x=["2","4","C"]; 
var x="24C";

write("Hexadecimal number: ");

for(var i=0;i<x.length;i++) {
 write(x[i]);
 }

writeln();
writeln();

var d=0;
var posvalue=1;

for(var i=1;i<x.length;i++) {
 posvalue*=16;
 }

for(var i=0;i<x.length;i++) {
 var sz;
 switch(x[i]) {
  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(x[i]);  
  }
 writeln("   Digit           : "+sz);
 writeln("   Positional value: "+posvalue);
 var r=sz*posvalue;
 writeln("      Partial sum: "+r);
 d+=r;
 posvalue/=16;
 }

writeln();

writeln("Decimal number: "+d);

writeln("__________");

Finally, we will introduce a very important program structure. The above JavaScript program can also be implemented by creating a function. Notice that both the function that converts hexadecimal digits to decimal ones and the program that executes the full conversion have become much simpler.

The program is as follows: 

// converting a hexadecimal number to a decimal number 

function hex2dec(h) {
 var sz;
 switch(h) {
  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(h);  
  }
 return sz;
 }

var x="24C";

write("Hexadecimal number: "+x);
writeln();

var d=0;
var h=1;

var i=1;
while(i<x.length) {
 h=h*16;
 i=i+1;
 }

i=0;
while(i<x.length) {
 var sz;
 sz=hex2dec(x[i]);
 var r=sz*h;
 d=d+r;
 h=h/16;
 i=i+1;
 }

writeln("Decimal number: "+d);

writeln("__________");

Examples of algorithms:
3.1. converting a decimal number to a binary number

conversion of an integer

Example: 31410 = ?2

division quotient remainder
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

Result:
31410 = 1|0011|10102

Note: since a binary number usually consists of quite a lot of digits (i.e. it often seems to be "long"), it is useful to divide the digits into groups of four from the right (using a separator, e.g. the | character).

Check:
1|0011|10102 = 1*28 + 1*25 + 1*24 + 1*23 + 1*21 = 256 + 32 + 16 + 8 + 2 = 31410 (ok)

The JavaScript program implementing the above algorithm is as follows: 

// converting a decimal number to a binary number by divisions

var x=314; 

writeln("Decimal number: "+x);
writeln();

var b="";
var q=1;

while(q>0) {
 q=Math.trunc(x/2); // integer division!!
 write("   Quotient: "+q); 
 if(x%2==1) {
  b="1"+b;
  writeln(", remainder: "+1);
  }
 else {
  b="0"+b;
  writeln(", remainder: "+0);  
  }
 x=q;
 }

writeln();
writeln("Binary number: "+b);

writeln("__________");

We can also create a JavaScript program without integer division: 

// converting a decimal number to a binary number by divisions (version 2)

var x=114; 

writeln("Decimal number: "+x);
writeln();

var b="";

while(x>0) {
 if(x%2==1) {
  b="1"+b;
  x=x-1;
  }
 else {
  b="0"+b;
  }
 x=x/2;
 }

writeln("Binary number: "+b);

writeln("__________");

With small modifications we can create a program which converts a decimal number to a hexadecimal number: 

// converting a decimal number to a hexadecimal number by divisions

var x=128;
var hexdigit="0123456789ABCDEF";

writeln("Decimal number: "+x);
writeln();

var b="";

while(x>0) {
 var h=x%16;
 if(h!=0) {
  b=hexdigit[h]+b;
  x=x-h;
  }
 else {
  b="0"+b;
  }
 x=x/16;
 }

writeln("Hexadecimal number: "+b);

writeln("__________");

Powers of two

An alternative way to convert a decimal integer to a binary number is as follows:

  1. find the highest power of two that is less than or equal to the number to be converted; that will be the highest positional value of the binary number
    • the digit corresponding to the found positional value will be '1';
  2. subtract the found positional value from the decimal number to be converted;
  3. considering the above result of the subtraction as a decimal number to be converted, we repeat steps 1 and 2 until the result of the subtraction is zero;
  4. in the binary notation of the decimal number to be converted, the digits to which we have not assigned the value '1' will have the value '0'.

Példa: 31410 = ?2

power of two decimal number to be converted
result of the subtraction 		binary digit
314
28=256 314−256=58 1
27=128 58<128 0
26=64 58<64 0
25=32 58−32=26 1
24=16 26−16=10 1
23=8 10−8=2 1
22=4 2<4 0
21=2 2−2=0 1
20=1 0<1 0

Result:
31410 = 1|0011|10102

The JavaScript program implementing the above algorithm is as follows: 

// converting a decimal number to a binary number by subtractions

var x=314; 

writeln("Decimal number: "+x);
writeln();

var b="";
var posvalue=1;

while(2*posvalue<=x) {
 posvalue*=2;
 }

while(posvalue>=1) {
 if(posvalue<=x) {
  b+="1";
  writeln("   Digit:            "+1);
  writeln("   Positional value: "+posvalue);
  x-=posvalue;
  }
 else {
  b+="0";
  writeln("   Digit:            "+0);
  writeln("   Positional value: "+posvalue);
  }
 posvalue/=2;
 }

writeln();
writeln("Binary number: "+b);

writeln("__________");

Examples of algorithms:
3.2. converting a decimal number to a binary number

conversion of a fraction

For the sake of simplicity, let's assume that the decimal fraction to be converted is positive and less than 1.

Example: 0.687510 = ?2

  1. multiply the decimal number to be converted (e.g. 0.6875) by 2 until
    • the fractional part is 0, or
    • a given sequence of binary digits shows endless repetition.
  2. write the whole part of the product (which can be 0 or 1), and then subtract it from the product
  3. if the algorithm continues, the result of the above subtraction (i.e. the fractional part of the above product) is multiplied by 2 again
  4. repeat from step 2
  5. the binary notation of the decimal fraction to be converted is obtained by writing down the written whole parts of the products in the original order after the starting 0. of the number (e.g. 0.1011)
product whole part fractional part
0.6875
0.6875*2= 1.375 1 0.375
0.375*2= 0.75 0 0.75
0.75*2= 1.5 1 0.5
0.5*2= 1 1 0

Result:
0.687510 = 0.10112

Notes:
(1) in the case of more than four binary digits, it is also worth dividing the sequence of digits into groups of four (from the left, just after the "binary point");
(2) if the whole part of the decimal number to be converted is greater than 0, convert the whole part and the fractional part of the decimal number separately into a binary number.

Check:
0.10112 = 1*2−1 + 1*2−3 + 1*2−4 = 1/2 + 1/8 + 1/16 = 11/16 = 0.687510 (ok)

The JavaScript program implementing the above algorithm is as follows: 

// converting a decimal fraction to a binary one 

var x=0.6875;

writeln("Decimal fraction: "+x);
writeln();

var maxi=50;
var s="";

var i=1;
while(x>0 && i<=maxi) {
 x*=2;
 if(x<1) {
  write("   whole part: 0,");
  s+="0";
  }
 else {
  write("   whole part: 1,");
  s+="1";
  x=x-1;
  }
 writeln("   fractional part: "+x);
 if(i%4==0) {
  writeln("..... "+i+". cycle .....");
  s+=" ";
  }
 i++;
 }

writeln();
writeln("Binary fraction (first "+maxi+" binary digits): 0."+s);

writeln("__________");

When converting a (finite) decimal fraction to a binary one, the algorithm sometimes provides an infinite number of steps, that is, we can get an infinite repeating binary fraction corresponding to a rational number (represented by the given decimal fraction).

Let us examine carefully two other examples:
    (a) 0.4510 = ?2
    (b) 0.810 = ?2

(a) converting 0.45 to binary fraction
step product whole part fractional part comment
...

Result:
0.4510 = 0.01110011001100...2

(b) converting 0.8 to a binary fraction
step product whole part fractional part comment

Result:
0.810 = 0.110011001100...2

Let us observe, that the repeating group of binary digits begins when the same fractional part occurs as the left-side factor in the product in the 'step' column. E.g. in case x=0.45 the repeating group begins at the first 0.80*2 product; and in case x=0.8 the repeating group begins at the first 0.80*2 product.

If we store all values of 'x' in an array of numbers (named 'a'), we can examine whether a new value of 'x' occurs in the array or not. If 'yes' we found a repeating group so the algorithm ends. The following program illustrates this idea. 

// converting a decimal fraction to a binary one (ver. 2)

function setlength(s,n) {
 var t=s.substring(0,n)
 while(t.length<n) {
  t=t+"0";
  }
 return t;
 }

function findx(x1) {
 var p=-1;
 for(var i=0;i<ptr;i++) {
  if(a[i]==x1) { 
   p=i;
   break; 
   }
  }
 return p;
 }

function binfrac(s,pos) {
 var t="0.";
 for(var i=0;i<pos;i++) {
  t=t+s[i];
  }
 t=t+"[";
 for(var i=pos;i<s.length;i++) {
  t=t+s[i];
  }
 t=t+"]...";
 return t;
 }

var x=0.45; // 0<x<1
var n=4; // limit the number of decimal digits
var a=new Array();
var ptr=0;

writeln("Decimal fraction: "+x);
writeln();

var maxi=50;
var pos=-1;
var s="";

var i=1;
while(x>0 && i<=maxi) {
 var x1=setlength(""+x,n+2);
 var pos=findx(x1);
 if(pos>=0) {
  x*=2;
  var x2=setlength(""+x,n+2);
  write("   x="+x1+" -> 2*x="+x2);
  writeln(" [repeating]");
  break;
  }
 a[ptr]=x1;
 ptr++;
 x*=2;
 var x2=setlength(""+x,n+2);
 write("   x="+x1+" -> 2*x="+x2);
 var t="";
 if(x<1) {
  t="0";
  s+=t;
  }
 else {
  t="1";
  s+=t;
  x=x-1;
  }
 writeln(" ("+t+")");
 i++;
 }

writeln();
if(pos>=0) {
 writeln("Binary fraction: "+binfrac(s,pos));
 }
else {
 writeln("Binary fraction (first "+maxi+" binary digits): 0."+s);
 }

writeln("__________");

The problem of the program is that we need to limit the number of decimal digits in order to find one of the previous values stored in the array 'a' (see the a[i]==x1 comparison within the 'findx' function).

In general, when computing with decimal fractions, the product represented in the second column of the tables (a) and (b) before is always calculated in a finite number of bits which, in turn, may result in an approximate value. Therefore it is worth using rational fractions (represented by quotients of whole numbers) instead of decimal fractions when performing a conversion, e.g. 4/5 instead of 0.8 or 5/7 instead of 0.714285714285... (see the example below).

Example: 5/7=0.714285714285...10 = ?2

product whole part fractional part rational fraction

Result:
5/710 = 0.101101101...2

Now let us see the algorithm converting the rational fraction 5/7 directly to a binary fraction.

converting 5/7 product fractional part whole part comment
2*5= 10 10-7=3 1
2*3= 6 6 0
2*6= 12 12-7=5 1
2*5= 10 10-7=3 1 (repetition begins)
...

Result:
5/710 = 0.101101101...2

The corresponding JavaScript program is as follows: 

// converting a rational fraction to a binary one

/* condition: the rational fraction is positive and less than one (i.e. x<y) */

var x=5, y=7;

writeln("Rational fraction: "+x+"/"+y);
writeln();

var maxi=50;
var s="";

var i=1;
while(x>0 && i<=maxi) {
 if(2*x<y) {
  write("   whole part: 0,");
  s+="0";
  x=2*x;
  }
 else {
  write("   whole part: 1,");
  s+="1";
  x=2*x-y;
  }
 writeln("   fractional part: "+x+"/"+y);
 if(i%4==0) {
  writeln("..... "+i+". cycle .....");
  s+=" ";
  }
 i++;
 }

writeln();
writeln("Result (first "+maxi+" digits): 0."+s);

writeln("__________");

In the next section, we will learn how to check these results.

Boda István, 2024.