Technical Computer Science
Number Representations

• The decimal system, which we use in everyday life, has ten number symbols:
  $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$
• The absolute position of the characters is important to determine the numerical value
• Example: $123 \ne 321$
• Example: $5124 = 5 \cdot 1000 + 1 \cdot 100 + 2 \cdot 10 + 4$
• The numerical value $w$ is computed as follows from the digits $z_{n-1}, \dots, z_1, z_0$ of a decimal number:
  
  $\begin{aligned}w &= z_{n-1} \cdot 1\underbrace{0\dots0}_{n-1} + \dots z_2 \cdot 100 + z_1 \cdot 10 + \ z_0 \cdot 1 =\\ &=\sum\limits_{i=0}^{n-1} z_i \cdot 10^i\end{aligned}$
• The decimal system is a so-called positional notation
• The decimal system is a positional notation with a base of 10

• The base $b=2$ with an alphabet of two number symbols, $0$ and $1$, is of particular importance in computer science because two symbols can be easily encoded electrically:
  • "no current flows" typically corresponds to $0$
  • "current flows" corresponds to $1$
  • Each digit of a binary number is referred to as a "bit" ("binary digit")
  • 1 bit is therefore the smallest amount of information that can be stored
  • 8 bits are referred to as 1 byte
• The bit sequence $(01001101)_2$ corresponds to the decimal number $(77)_{10}$
  
  $\begin{align}&(01001101)_2 \\ &= 0 \cdot 2^7 + 1 \cdot 2^6 + 0 \cdot 2^5 + 0 \cdot 2^4+ 1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0\\ &=0 \cdot 128 + 1 \cdot 64 + 0 \cdot32 + 0 \cdot 16+ 1 \cdot 8 + 1 \cdot 4 + 0 \cdot 2 + 1 \cdot 1\\ &=64 + 8 + 4 + 1\\ &=77 \end{align}$

• A rational number $w \in \mathbb{Q}$ can also be specified in the b-adic representation
• For this purpose, the fractional part is represented by negative exponents
• Example from the decimal system, which we are familiar with:
  
  $913,64 = 9 \cdot 10^2 + 1 \cdot 10^1 + 3 \cdot 10^0 + 6 \cdot 10^{-1} + 4 \cdot 10^{-2}$
• This can be generalized again:
  $\begin{align} w &= (z_{n-1}\dots z_2 z_1 z_0, z_{-1} \dots z_{-m})_b\\ &= \sum\limits_{i=-m}^{n-1} z_i \cdot b^i \end{align}$
  where $n$ indicates the number of digits before the decimal point
  and $m$ indicates the number of digits after the decimal point
• Example in the binary system:
  
  $\begin{align}(11,101)_2 &= 1 \cdot 2^1 + 1 \cdot 2^0 + 1 \cdot 2^{-1} + 0 \cdot 2^{-2} + 1 \cdot 2^{-3} \\ &= 2 + 1 + 0.5 + 0,125 = (3,625)_{10}\end{align}$

• For many powers of ten, there are standardized metric prefixes that can be placed before the actual physical units, e.g. 1000 m = 1 km

• When talking about 1 kByte (kilobyte) in computer science, this does not always refer to 1000 bytes, but often to 1024 bytes. This leads to confusion. Therefore, it would be better to use the following IEC-specified prefixes for the powers of 1024:

• To develop an algorithm for converting between number systems, let us consider what happens when we divide the formula for the b-adic representation by the base $b$:
  $\begin{aligned}w = \sum\limits_{i=0}^{n-1} z_i \cdot b^i\Leftrightarrow \frac{w}{b} &= \frac{1}{b}\sum\limits_{i=0}^{n-1} z_i \cdot b^i\\ &= \underbrace{\left(\sum\limits_{i=0}^{n-2} z_{i+1} \cdot b^i\right)}_{s_1} + \frac{z_0}{b} \end{aligned}$
• The first term $s_1$ is the integer result of the division and $z_0$ is the remainder of the division
• This showed that the last digit $z_0$ can be calculated from the remainder of the division with the target base $b$
• The integer result of the division represents the numerical value of the remaining digits (without $z_0$). All target digits can be determined by recursive application.

• Example: Converting the decimal number 6485 to binary:

6485 / 2 = 3242  remainder 1
3242 / 2 = 1621  remainder 0
1621 / 2 =  810  remainder 1
 810 / 2 =  405  remainder 0
 405 / 2 =  202  remainder 1
 202 / 2 =  101  remainder 0
 101 / 2 =   50  remainder 1
  50 / 2 =   25  remainder 0
  25 / 2 =   12  remainder 1
  12 / 2 =    6  remainder 0
   6 / 2 =    3  remainder 0
   3 / 2 =    1  remainder 1
   1 / 2 =    0  remainder 1

• The algorithm terminates if the result of the division is equal to zero
• The binary number can be read from bottom to top using the remainders: $(1100101010101)_2$
• Note: If such an algorithm has to be implemented, the remainder of the division can be computed using the modulo operation: 6485 mod 2 = 1

• Example: Conversion of $(360)_7$ into the quinary system (base 5)
• First, $(360)_7$ must be converted to decimal:
  
  $(360)_7 = 3 \cdot 49 + 6 \cdot 7 + 0 \cdot 1 = (189)_{10}$
• Then we convert $189_{10}$ into the quinary system:

189 / 5 =  37  Rest 4
 37 / 5 =   7  Rest 2
  7 / 5 =   1  Rest 2
  1 / 5 =   0  Rest 1

• The result can be read off again from the remainders: $(1224)_{5}$
• Instead of taking the detour via the decimal system, we could theoretically apply the procedure directly in the 7-based system. However, then we would have to perform the operations (division and calculation of the remainder) in the 7-based system, which we as humans are not used to.

• To convert rational numbers, we consider the integer and fractional parts separately:
  $\begin{align} w &= (z_{n-1}\dots z_2 z_1 z_0, z_{-1} \dots z_{-m})_b\\ &= \sum\limits_{i=-m}^{n-1} z_i \cdot b^i \\ &= \left(\sum\limits_{i=0}^{n-1} z_i \cdot b^i\right) + \left(\sum\limits_{i=-m}^{-1} z_i \cdot b^i\right)\end{align}$
• The conversion for the integer part is known, so we now only consider the fractional part $\tilde{w}$:
  $\begin{align} \tilde{w} &= (0, z_{-1} \dots z_{-m})_b = \left(\sum\limits_{i=-m}^{-1} z_i \cdot b^i\right)\end{align}$

• In contrast to the approach used for the conversion of the integer part (the remainder of the division), the fractional part must be multiplied by the base $b$:
  $\begin{aligned}\tilde{w}= \sum\limits_{i=-m}^{-1} z_i \cdot b^i \Leftrightarrow \tilde{w} \cdot b &= b \sum\limits_{i=-m}^{-1} z_i \cdot b^i\\ &= \left(\sum\limits_{i=-m}^{-2} z_{i} \cdot b^{i+1}\right) + z_{-1} \end{aligned}$
• The term $z_{-1}$ is the only part that can be $\ge 1$. Thus, the integer part of $\tilde{w} \cdot b$ is equal to $z_{-1}$
• The fractional part of $\tilde{w} \cdot b$ represents the numerical value of the remaining digits (without $z_{-1})$. All other digits can be determined by recursive application.