domenica 14 febbraio 2016

Base conversion of unsigned floating point numbers

One of the most successful Android apps I published on Google Play is certainly Base Converter. It converts numbers from decimal numeral system to binary, hexadecimal, octal and vice versa. Some users have recently asked me an explanation for the algorithms used to perform the conversion, but it is not convenient to integrate an article within an app, so I wrote this paper to satisfy their request. For convenience I will not write all the algorithms used to perform the conversion, however the techniques shown below will make you able to convert between the four bases (you have to use two algorithms if necessary).


Converting floating point bin 1011011.11001 to dec

We start converting the integer part:

$$1011011_{2} = 1 \cdot 2^{6} + 0 \cdot 2^{5} + 1 \cdot 2^{4} + 1 \cdot 2^{3} + 0 \cdot 2^{2} + 1 \cdot 2^{1} + 1 \cdot 2^{0}$$
$$1011011_{2} = 64 + 16 + 8 + 2 + 1 = 91_{10}$$
Then we convert the fractional part:

$$0.11001_{2} = 1 \cdot 2^{-1} + 1 \cdot 2^{-2} + 0 \cdot 2^{-3} + 0 \cdot 2^{-4} + 1 \cdot 2^{-5}$$
$$0.11001_{2} = 1 \cdot \frac{1}{2^{1}} + 1 \cdot \frac{1}{2^{2}} + 0 \cdot \frac{1}{2^{3}} + 0 \cdot \frac{1}{2^{4}} + 1 \cdot \frac{1}{2^{5}}$$
$$0.11001_{2} = 0.5 + 0.25 + 0.03125 = 0.78125_{10}$$
So we obtain:

$$1011011.11001_{2} = 91.78125_{10}$$

Converting floating point dec 273.241 to bin

As above we start from the integer part. We divide the integer part by two, annotating the remainder of the division. Then we divide the result of the division by two, and we write again the remainder of the division (before the previous one). The procedure stops when the division result is zero.

$$\frac{273}{2} = 136, \, r = \textbf{1} \longrightarrow \textbf{1}$$
$$\frac{136}{2} = 68, \, r = \textbf{0} \longrightarrow \textbf{0}1$$
$$\frac{68}{2} = 34, \, r = \textbf{0} \longrightarrow \textbf{0}01$$
$$\frac{34}{2} = 17, \, r = \textbf{0} \longrightarrow \textbf{0}001$$
$$\frac{17}{2} = 8, \, r = \textbf{1} \longrightarrow \textbf{1}0001$$
$$\frac{8}{2} = 4, \, r = \textbf{0} \longrightarrow \textbf{0}10001$$
$$\frac{4}{2} = 2, \, r = \textbf{0} \longrightarrow \textbf{0}010001$$
$$\frac{2}{2} = 1, \, r = \textbf{0} \longrightarrow \textbf{0}0010001$$
$$\frac{1}{2} = 0, \, r = \textbf{1} \longrightarrow \textbf{1}00010001$$
Now we convert the fractional part. In this case the fractional part is multiplied by two, and we annote the integer part of the result. Then we multiply the result of the previous multiplication by two, and we write again the integer part of the result (after the previous one). The algorthm stops when the result of the multiplication is zero, or when you get sufficient significant digits.

$$0.241 \cdot 2 = \textbf{0}.482 \longrightarrow 0.\textbf{0}$$
$$0.482 \cdot 2 = \textbf{0}.964 \longrightarrow 0.0\textbf{0}$$
$$0.964 \cdot 2 = \textbf{1}.928 \longrightarrow 0.00\textbf{1}$$
$$0.928 \cdot 2 = \textbf{1}.856 \longrightarrow 0.001\textbf{1}$$
$$0.856 \cdot 2 = \textbf{1}.712 \longrightarrow 0.0011\textbf{1}$$
$$0.712 \cdot 2 = \textbf{1}.424 \longrightarrow 0.00111\textbf{1}$$
$$0.424 \cdot 2 = \textbf{0}.848 \longrightarrow 0.001111\textbf{0}$$
$$0.848 \cdot 2 = \textbf{1}.696 \longrightarrow 0.0011110\textbf{1}$$
So the final result is:
$$273.241_{10} = 100010001.00111101_{2}$$

Converting floating point dec 273.241 to hex

The procedure is similar to the previous one, we only change the target radix to 16:

$$\frac{273}{16} = 17, \, r = \textbf{1} \longrightarrow \textbf{1}$$
$$\frac{17}{16} = 1 , \, r = \textbf{1} \longrightarrow \textbf{1}1$$
$$\frac{68}{16} = 0, \, r = \textbf{1} \longrightarrow \textbf{1}11$$

About the fractional part we change the radix to 16 again, in addition we convert the result of the multiplication from decimal to hexadecimal (for this conversion you can refer to this table):

$$0.241 \cdot 16 = \textbf{3}.856 \longrightarrow 0.\textbf{3}$$
$$0.856 \cdot 16 = \textbf{13}.696 \longrightarrow 0.3\textbf{D}$$
$$0.696 \cdot 16 = \textbf{11}.136 \longrightarrow 0.3D\textbf{B}$$
$$0.136 \cdot 16 = \textbf{2}.176\longrightarrow 0.3DB\textbf{2}$$
$$0.176 \cdot 16 = \textbf{2}.816 \longrightarrow 0.3DB2\textbf{2}$$

So we obtain:
$$273.241_{10} = 111.3DB22_{16}$$

Converting floating point dec 273.241 to oct

We use the same algorithm of the two previous sections, obviously in this case the target radix is 8:

$$\frac{273}{8} = 34, \, r = \textbf{1} \longrightarrow \textbf{1}$$
$$\frac{34}{8} = 4 , \, r = \textbf{2} \longrightarrow \textbf{2}1$$

$$\frac{68}{8} = 0, \, r = \textbf{4} \longrightarrow \textbf{4}21$$
Now we convert the fractional part:

$$0.241 \cdot 8 = \textbf{1}.928 \longrightarrow 0.\textbf{1}$$
$$0.928 \cdot 8 = \textbf{7}.424 \longrightarrow 0.1\textbf{7}$$
$$0.424 \cdot 8 = \textbf{3}.392 \longrightarrow 0.17\textbf{3}$$
$$0.392 \cdot 8 = \textbf{3}.136 \longrightarrow 0.173\textbf{3}$$
$$0.136 \cdot 8 = \textbf{1}.088 \longrightarrow 0.1733\textbf{1}$$

So the result is:

$$273.241_{10} = 421.17331_{8}$$

Converting floating point bin 101001011.1010011011 to hex

This is the number we want to convert:

$$\texttt{101001011.1010011011}$$
First of all we split the digits in groups made of four numbers, possibly we add additional zero digits on the left in the integer part, and on the right of the fractional part to fill the first and the last group:

$${\color{red}{\texttt{1}}} {\color{black}{\texttt{0100}}}  {\color{green}{\texttt{1011}}} \texttt{.} {\color{brown}{\texttt{1010}}} {\color{blue}{\texttt{0110}}} {\color{purple}{\texttt{11}}}$$
$${\color{red}{\textbf{000}}} {\color{red}{\texttt{1}}} \quad {\color{black}{\texttt{0100}}} \quad {\color{green}{\texttt{1011}}} \quad \texttt{.} \quad {\color{brown}{\texttt{1010}}} \quad {\color{blue}{\texttt{0110}}} \quad {\color{purple}{\texttt{11}}} {\color{purple}{\textbf{00}}}$$
Then we convert the binary groups to the hexadecimal base (for this conversion you can refer to this table).

$${\color{red}{\texttt{1}}} \quad {\color{black}{\texttt{4}}} \quad {\color{green}{\texttt{B}}} \quad \texttt{.} \quad {\color{brown}{\texttt{A}}} \quad {\color{blue}{\texttt{6}}} \quad {\color{purple}{\texttt{C}}}$$
So the result is:
$$\texttt{101001011.1010011011}_{2} = \texttt{14B.A6C}_{10}$$
To perform the conversion from hexadecimal to decimal you have to do the same procedure shown above, by reversing the steps.


Converting floating point bin 101001011.1010011011 to oct

$$\texttt{101001011.1010011011}$$
We use the same procedure of the previous section, but the groups are now composed of three digits.
$${\color{red}{\texttt{101}}} {\color{black}{\texttt{001}}}  {\color{green}{\texttt{011}}} \texttt{.} {\color{brown}{\texttt{101}}} {\color{blue}{\texttt{001}}} {\color{purple}{\texttt{101}}} {\color{orange}{\texttt{1}}}$$
$${\color{red}{\texttt{101}}} \quad {\color{black}{\texttt{001}}} \quad {\color{green}{\texttt{011}}} \quad \texttt{.} \quad {\color{brown}{\texttt{101}}} \quad {\color{blue}{\texttt{001}}} \quad {\color{purple}{\texttt{101}}} \quad {\color{orange}{\texttt{1}}} {\color{orange}{\textbf{00}}}$$
$${\color{red}{\texttt{5}}} \quad {\color{black}{\texttt{1}}} \quad {\color{green}{\texttt{3}}} \quad \texttt{.} \quad {\color{brown}{\texttt{5}}} \quad {\color{blue}{\texttt{1}}} \quad {\color{purple}{\texttt{5}}} \quad {\color{orange}{\texttt{4}}}$$
$$\texttt{101001011.1010011011} = \texttt{513.5154}$$


Quick conversion table for binary and hexadecimal numbers

Binary Hexadecimal
$$\texttt{0000}$$ $$\texttt{0}$$
$$\texttt{0001}$$ $$\texttt{1}$$
$$\texttt{0010}$$ $$\texttt{2}$$
$$\texttt{0011}$$ $$\texttt{3}$$
$$\texttt{0100}$$ $$\texttt{4}$$
$$\texttt{0101}$$ $$\texttt{5}$$
$$\texttt{0110}$$ $$\texttt{6}$$
$$\texttt{0111}$$ $$\texttt{7}$$
$$\texttt{1000}$$ $$\texttt{8}$$
$$\texttt{1001}$$ $$\texttt{9}$$
$$\texttt{1010}$$ $$\texttt{A}$$
$$\texttt{1011}$$ $$\texttt{B}$$
$$\texttt{1100}$$ $$\texttt{C}$$
$$\texttt{1101}$$ $$\texttt{D}$$
$$\texttt{1110}$$ $$\texttt{E}$$
$$\texttt{1111}$$ $$\texttt{F}$$