Representation of Numbers

Representation of numbers

So far we have only dealt with logical variables and performed logical operations. We will see in this section how to represent and manipulate numbers.

Natural numbers

General Representation

A natural number $N$ can be represented in a base $b$ by a $n$ -tuple $(a_{n - 1}, a_{n - 2}, \dots, a_{1}, a_{0})$ such that ¹:

$N = a_{n - 1} \cdot b^{n - 1} + a_{n - 2} \cdot b^{n - 2} + \dots + a_{1} \cdot b^{1} + a_{0} \cdot b^{0}$

In this representation:

$a_{i}$ is a digit of rank $i$ and belongs to a set of $b$ symbols ( $0$ to $b - 1$ )
$a_{n - 1}$ is called the most significant digit
$a_{0}$ is called the least significant digit

The most commonly used bases² are:

$b = 10$ : decimal representation, $a_{i} \in {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}$
$b = 16$ : hexadecimal representation,
$a_{i} \in {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F}$
$b = 8$ : octal representation, $a_{i} \in {0, 1, 2, 3, 4, 5, 6, 7}$
$b = 2$ : binary representation, $a_{i} \in {0, 1}$ . A binary digit is also called bit (short for binary digit)

Unsigned binary representation

We will focus in the following on the representation of numbers in binary (base 2). In this base, an unsigned integer can be represented by the $n$ -tuple $(a_{n - 1}, a_{n - 2}, \dots, a_{1}, a_{0})$ such that:

$N = a_{n - 1} \cdot 2^{n - 1} + a_{n - 2} \cdot 2^{n - 2} + \dots + a_{1} \cdot 2^{1} + a_{0} \cdot 2^{0}$

Where:

$a_{i}$ is a bit (it belongs to a set of $2$ symbols: $0$ or $1$ )
$a_{n - 1}$ is called the most significant bit (MSB)
$a_{0}$ is called the least significant bit (LSB)

Conversion between hexadecimal and binary

It is very simple to go from a number represented in hexadecimal to a number represented as an unsigned binary. Just concatenate the 4-bit binary representation of each of the hexadecimal digits.

Example:

$A 1 F_{(16)} = 10100001111 1_{(2)}$

We have:

$A 1 F_{(16)} = 10 \cdot 1 6^{2} + 1 \cdot 1 6^{1} + 15 \cdot 1 6^{0} = (1 \cdot 2^{3} + 0 \cdot 2^{2} + 1 \cdot 2^{1} + 0 \cdot 2^{0}) \cdot 1 6^{2} + (0 \cdot 2^{3} + 0 \cdot 2^{2} + 0 \cdot 2^{1} + 1 \cdot 2^{0}) \cdot 1 6^{1} + (1 \cdot 2^{3} + 1 \cdot 2^{2} + 1 \cdot 2^{1} + 1 \cdot 2^{0}) \cdot 1 6^{0} = 1 \cdot 2^{11} + 0 \cdot 2^{10} + 1 \cdot 2^{9} + 0 \cdot 2^{8} + 0 \cdot 2^{7} + 0 \cdot 2^{6} + 0 \cdot 2^{5} + 1 \cdot 2^{4} + 1 \cdot 2^{3} + 1 \cdot 2^{2} + 1 \cdot 2^{1} + 1 \cdot 2^{0} = 10100001111 1_{(2)}$

Similarly, to go from an unsigned binary representation to a hexadecimal representation, it suffices to group the bits 4 by 4 (starting from the least significant bits), thereby transforming each of the groups into a hexadecimal digit.

Example:

$101011000 0_{(2)} = 2 B 0_{(16)}$

Modulo binary representation

In practice, in hardware, numbers are represented and manipulated over a finite fixed number of bits. So a number $N$ will be represented, modulo $2^{n}$ , on $n$ bits. Using $n$ bits, it is therefore possible to represent the natural numbers in the range $[0, 2^{n} - 1$ ].

Signed integers

There are several methods to represent signed integers. The most commonly used is the representation in two’s complement (CA2).

As seen previously, using $n$ bits, numbers are represented modulo $2^{n}$ , i.e. $2^{n}$ has the same representation as $0$ , $2^{n} + 1$ has the same representation as $1$ , etc.

If we extend this principle to negative numbers, we would require $- 1$ to have the same representation as $2^{n} - 1$ (i.e. $11 \dots 1 1_{(2)}$ ), that $- 2$ has the same representation as $2^{n} - 2$ (i.e. $11 \dots 1 0_{(2)}$ ), etc.

By convention, in the 2’s complement representation, the numbers whose most significant bit is 1 will be considered as negative numbers, and the numbers whose most significant bit is 0 will be considered as positive numbers³.

In two’s complement, we can therefore represent, using $n$ bits, the signed numbers in the range $[- 2^{n - 1}, 2^{n - 1} - 1$ ].

Example: 4-bit representation ( $n = 4$ ):

CA2 Binary	Decimal	Unsigned Binary	Decimal
$1000$	$- 8$	$1000$	$8$
$1001$	$- 7$	$1001$	$9$
$1010$	$- 6$	$1010$	$10$
$1011$	$- 5$	$1011$	$11$
$1100$	$- 4$	$1100$	$12$
$1101$	$- 3$	$1101$	$13$
$1110$	$- 2$	$1110$	$14$
$1111$	$- 1$	$1111$	$15$
$0000$	$0$	$0000$	$0$
$0001$	$1$	$0001$	$1$
$0010$	$2$	$0010$	$2$
$0011$	$3$	$0011$	$3$
$0100$	$4$	$0100$	$4$
$0101$	$5$	$0101$	$5$
$0110$	$6$	$0110$	$6$
$0111$	$7$	$0111$	$7$

From a mathematical point of view, a number $N$ represented as two’s complement with $n$ bits by $(a_{n - 1}, a_{n - 2}, \dots, a_{0})$ is given as:

$N = - a_{n - 1} 2^{n - 1} + i = 0 \sum n - 2 a_{i} 2^{i}$

Sign extension

Extension rules allow us to go from a number represented with $n$ bits to the same number represented with $n + m$ bits.

Unsigned integers

In the unsigned case (natural numbers), the extension consists of adding $m$ bits valued $0$ on the left (most significant bits).

Example: $9_{(10)}$ represented as an unsigned integer using $4$ bits gives us $100 1_{(2)}$ . Using $6$ bits, it is represented as $00100 1_{(2)}$ .

Two’s complement

In the case of a signed number represented in two’s complement, the extension is a little more complex because we must not forget that the most significant bit carries the information of the sign. For a two’s complement number, the extension is done by duplicating the most significant bit.

Examples: $- 7_{(10)}$ is represented with $4$ bits in two’s complement in the form $100 1_{(2)}$ . On $6$ bits, it is represented as $11100 1_{(2)}$ . $5_{(10)}$ is represented with $4$ bits in two’s complement as $010 1_{(2)}$ . On $6$ bits, it turns out as $00010 1_{(2)}$ .

Proof: Let $N = (a_{n - 1}, a_{n - 2}, \dots, a_{0})$ be a signed integer represented in two’s complement using $n$ bits.

$N = - a_{n - 1} 2^{n - 1} + i = 0 \sum n - 2 a_{i} 2^{i}$ $= - a_{n - 1} 2^{n - 1} \cdot (2 - 1) + i = 0 \sum n - 2 a_{i} 2^{i}$ $= - a_{n - 1} 2^{n} + a_{n - 1} 2^{n - 1} + i = 0 \sum n - 2 a_{i} 2^{i}$ $= - a_{n - 1} 2^{n} + i = 0 \sum n - 1 a_{i} 2^{i}$

Hence $N = (a_{n - 1}, a_{n - 1}, a_{n - 2}, \dots, a_{0})$ is its representation with $n + 1$ bits.

Summary

In conclusion, when we represent a number in binary, it is very important to specify the convention chosen (unsigned, two’s complement, fixed point…) as well as the number of bits.

Note that the operators $+$ and $\cdot$ take on their classical mathematical meaning here, i.e. addition and multiplication, unlike in the previous chapter where they corresponded to the logical operators OR and AND.

In the following, in case of risk of confusion, the base in which a number is represented will be indicated as a subscript, example: $10 0_{(10)}$ , $10 0_{(2)}$ , $10 0_{(16)}$

This keeps compatibility with the unsigned representation

⁴

Fixed because once the respective number of bits of the integer part and the fractional part are fixed, they do not change. There are other methods, including the floating-point representation — which you’ve probably heard of — which is significantly more complex to implement at the operational level and which we will therefore not discuss in this course.

INF107