14  Number Representation

Counting has a long history, as does the representation of numbers. At the beginning of numerical recording, there was a one-to-one representation. This means that each each object to be counted was represented by a symbol. This approach is not particularly efficient. Therefore, early in human history people started developing more compact representations of numbers.

(a) Five

(b) Twenty-four

Figure 14.1: Objects to count

14.1 One-to-one Number Representation

In a one-to-one number representations the objects in Figure 14.1 (a) could be represented by the objects in Figure 14.1 (b) by respectively.

14.2 Symbolic Number Representation

While the Romans were not the pioneers of representing numerical values through symbols, their system remains the most prominent historical example. Consequently, the Roman method for denoting the quantity of objects is illustrated in figures Figure 14.1 (a) (V) and Figure 14.1 (b) (XXIV).

Roman numerals are generally intuitive up to the number twelve; however, representing larger values increases complexity significantly. In principle, each symbol within a Roman numeral possesses a fixed value. An exception occurs only when a symbol of lesser value precedes one of greater value, indicating subtraction.

Furthermore, Roman numerals require considerable space. The current year becomes MMXXVI an increase in space consumption by 50% compared to the decimal 2026.

14.3 Number Representation and Positional Notation

14.3.1 Decimal Representation of Numbers

Unlike Roman numerals, decimal numerals possess both a face value and a positional value. For instance, the quantity of objects shown in Figure 14.1 (a) is represented by the digit 5, signifying five ones. In Figure 14.1 (b), the quantity becomes 24, representing two tens plus four ones.

When expressed as a formal calculation:

\[5 = 5 \times 10^0 \quad \text{and} \quad 24 = 2 \times 10^1 + 4 \times 10^0\]

This distinction demonstrates the mechanics of a positional numeral system:

• The face value (the digit itself) acts as a coefficient.
• The positional value (determined by the digit’s position) corresponds to a power of the base.

This differentiation between face and positional values enables a significantly more compact representation of numbers compared to additive symbolic systems such as Roman numerals.

14.3.2 Binary Representation of Numbers

A well-known joke in computer science circles goes:

There are 10 kinds of people:

• those who understand binary numbers, and
• those who don’t.

Understanding binary numbers is essential to appreciating this joke.

While decimal numbers are represented in formal calculations as products of single digits and powers of the base 10, binary numbers use base 2. The quantities shown in Figure 14.1 (a) and Figure 14.1 (b), when represented as binary numbers, are \(101_2\) and \(11000_2\), respectively.

Expressed as formal calculations:

\[ 5_{10} = 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 = 101_2 \]

and

\[ 24_{10} = 1 \times 2^4 + 1 \times 2^3 + 0 \times 2^2 + 0 \times 2^1 + 0 \times 2^0 = 11000_2 \]

One position in a binary number is called a bit (short for binary digit). Eight bits compose a byte, which is the smallest addressable unit of memory in most computer systems. For example, the ASCII code for the letter ‘A’ is stored in one byte: \(01000001_2\).

14.3.3 Hexadecimal Numbers

Hexadecimal numbers use base \(16_{10}\). Therefore, the quantities shown in Figure 14.1 (a) and Figure 14.1 (b) become \(5_{16}\) and \(18_{16}\), respectively.

Because the Arabic numerals used in the decimal system provide only ten digits (0–9), additional symbols are needed to represent hexadecimal numbers. The symbols chosen are the first six uppercase letters of the Latin alphabet. Thus, hexadecimal numbers are composed of the sixteen symbols: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, and F.

These numbers expressed as a formal calculation:

\[ 5_{10} = 5 \times 16^0 = 5_{16} \]

\[ 24_{10} = 1 \times 16^1 + 8 \times 16^0 = 18_{16} \]

Each hexadecimal digit represents exactly four bits (also called a nibble). Hexadecimal numbers are widely used in computer science as the follwing examples demonstrate:

• Memory addresses: 0x7FFFFFFF
• RGB color codes: #FF5733 (red: FF, green: 57, blue: 33)
• Binary-to-hex conversion: Each hex digit represents exactly four bits (e.g., \(\text{F}_{16} = 1111_2\)).

14.4 Number Conversion

The following sections describe the algorithms for the conversion of numbers from one representation to the other.

14.4.1 Decimal to Binary Numbers

First, an empty string is initialized to represent the binary number. In a loop, the number \(n\) to be converted is processed using the modulo 2 operation. The result of this operation is prepended as the most significant bit (to the far left) of the existing binary string. Subsequently, the number \(n\) is halved using integer division, and the result of this division becomes the new value of \(n\). This process is repeated until \(n\) reaches zero.

Nassi-Shneiderman diagram describing the algorithm (MSB = Most Significant Bit).

Task: Please implement the algorithm as described.

def decimal_to_binary(n: int) -> str:
    # TODO: implement the aforementioned algorithm 
    pass

14.4.2 Binary to Decimal Conversion

To convert binary numbers to decimal numbers, the formal calculation described above must be expressed algorithmically.

1. Initialize a counter \(e\) to zero.
2. Initialize a result variable \(r\) to zero.
3. Extract the rightmost digit \(d\) from the binary number.
4. Multiply \(d\) by \(2^e\) and add the result to \(r\).
5. Increment the counter \(e\) by one.
6. Repeat steps 3–5 for each remaining digit, moving from right to left, until all digits have been processed.

Nassi-Shneiderman diagram for the algorithm to convert binary numbers to decimal ones.

Task: Please implement the algorithm as described.

def binary_to_decimal(b: str) -> int:
    # TODO: implement the aforementioned algorithm
    pass

14.4.3 Decimal to Hexadecimal Conversion

To convert decimal numbers to hexadecimal numbers, the algorithm can be based on the binary conversion algorithm described earlier. However, hexadecimal representation requires additional symbols beyond 0–9. A lookup table maps decimal values to their hexadecimal equivalents, as shown in Table 14.1.

Table 14.1: Conversion table: decimal to hexadecimal.

Dec	Hex	Dec	Hex
0	0	8	8
1	1	9	9
2	2	10	A
3	3	11	B
4	4	12	C
5	5	13	D
6	6	14	E
7	7	15	F

Using this table, the conversion algorithm proceeds as follows:

1. Initialize an empty string to represent the hexadecimal number.
2. While \(n > 0\):
   1. Compute \(d = n \bmod 16\).
   2. Look up the hexadecimal digit corresponding to \(d\) in Table 14.1.
   3. Prepend this digit to the hexadecimal string.
   4. Update \(n\) using integer division: \(n \gets \lfloor n / 16 \rfloor\).
3. Return the hexadecimal string.

Nassi-Shneiderman diagram of the algorithm for the decimal to hexadecimal conversion.

Task: Please implement the algorithm as described.

def decimal_to_hexadecimal(d: int) -> str:
    # TODO: implement the aforementioned algorithm
    pass

14.4.4 Hexadecimal to Decimal Conversion

As with the conversion from decimal to hexadecimal, the reverse conversion requires only a small adaptation of the binary-to- decimal algorithm.

The formal calculation must account for the hexadecimal digit mapping shown in Table 14.1.

1. Initialize a counter \(e\) to zero.
2. Initialize a result variable \(r\) to zero.
3. Extract the rightmost digit \(d\) from the hexadecimal number.
4. Convert the digit \(d\) to its decimal equivalent using Table 14.1.
5. Multiply the decimal value by \(16^e\) and add the result to \(r\).
6. Increment the counter \(e\) by one.
7. Repeat steps 3–6 for each remaining digit, moving from right to left, until all digits have been processed.

Nassi-Shneiderman diagram of the algorithm for the hexadecimal to decimal conversion.

Task: Please implement the algorithm as described.

def hexadecimal_to_decimal(h: str) -> int:
    # TODO: implement the aforementioned algorithm
    pass

14.4.5 Decimal to Roman Numeral Conversion

To convert decimal numbers to Roman numerals, a greedy algorithm is employed that repeatedly subtracts the largest possible Roman value from the number.

Roman numerals use seven basic symbols and six subtractive combinations, as shown in Table 14.2.

Table 14.2: Roman numeral values in descending order.

Decimal	Roman	Type
1000	M	Basic
900	CM	Subtractive
500	D	Basic
400	CD	Subtractive
100	C	Basic
90	XC	Subtractive
50	L	Basic
40	XL	Subtractive
10	X	Basic
9	IX	Subtractive
5	V	Basic
4	IV	Subtractive
1	I	Basic

Using this table, the conversion algorithm proceeds as follows:

1. Initialize an empty string to represent the Roman numeral.
2. Initialize an index \(i\) to point to the first entry in Table 14.2 (largest value).
3. While the decimal number \(n > 0\):
   1. Let \(v\) be the decimal value at index \(i\).
   2. Let \(s\) be the Roman symbol(s) at index \(i\).
   3. If \(n \geq v\):
      • Append symbol \(s\) to the Roman numeral string.
      • Subtract \(v\) from \(n\): \(n \gets n - v\).
   4. Otherwise:
      • Increment index \(i\) to move to the next smaller value.
4. Return the Roman numeral string.

Example: Convert \(24_{10}\) to Roman numerals.

Step	\(n\)	\(i\)	\(v\)	\(s\)	Action	Result
1	24	0	1000	M	Skip	“”
2	24	1	900	CM	Skip	“”
3	24	2	500	D	Skip	“”
4	24	3	400	CD	Skip	“”
5	24	4	100	C	Skip	“”
6	24	5	90	XC	Skip	“”
7	24	6	50	L	Skip	“”
8	24	7	40	XL	Skip	“”
9	24	8	10	X	Append	“X”
10	14	8	10	X	Append	“XX”
11	4	8	10	X	Skip	“XX”
12	4	9	9	IX	Skip	“XX”
13	4	10	5	V	Skip	“XX”
14	4	11	4	IV	Append	“XXIV”
15	0	—	—	—	Done	“XXIV”

Result: \(24_{10} = \text{XXIV}\)

Nassi-Shneiderman diagram of the algorithm for decimal to Roman numeral conversion.

Task: Please implement the algorithm as described.

def decimal_to_roman(d: int) -> str:
    # TODO: implement the aforementioned algorithm
    pass

Figure 14.1 (a): Five Figure 14.1 (b): Twenty-four Nassi-Shneiderman diagram describing the algorithm (MSB = Most Significant Bit). Nassi-Shneiderman diagram for the algorithm to convert binary numbers to decimal ones. Nassi-Shneiderman diagram of the algorithm for the decimal to hexadecimal conversion. Nassi-Shneiderman diagram of the algorithm for the hexadecimal to decimal conversion. Nassi-Shneiderman diagram of the algorithm for decimal to Roman numeral conversion.