Fundamentals of Informatics

Various representation of numbers in digital computers

In digital computers, data is represented in binary notation, as sequences of bits. In the following, we assume that the data is stored in an 'n' bit storage unit called a register. In a register, 'n' different bits can be stored independently which allows a total of m=2ⁿ different bit variations. So an 'n' bit register can store 'm' different (binary coded) data. The number 'm' is also called the modulus of the register.
For example,
– the modulus of an 8 bit register is m=256;
– the modulus of a 16 bit register is m=65536;
– the modulus of a 24 bit register is m=16,777,216;
– the modulus of a 32 bit register is m=4,294,967,296.

Exactly m=2ⁿ different variations of binary coded data can be stored in an 'n' bit register.

Since we store individual bits in a register, an 'n' bit register can also be thought of as a series of one-bit storage units denoted by b₀, b₁, ... respectively (where each unit has a value of 0 or 1). Using such notation, a register can be described in the form of
    b_n−1b_n−2...b₂b₁b₀
where b_n−1 stores (or represents) the most significant bit (MSB), and b₀ the least significant bit (LSB).
The meaning of MSB and LSB depends on the actual represention of data, e.g. when we deal with integers represented in a binary number system (using direct coding), MSB corresponds to the bit with the highest positional value, and LSB corresponds to the bit having lowest positional value (i.e. the number of ones).
In the case of the representation of signed numbers (more precisely, when the sequence of bits stored in the register is interpreted as a signed number, e.g. when using two's complement representation of binary integers or floating point representation of real numbers), the leftmost bit usually specifies the sign of the number:
    for b_n−1=0, the number stored in the register is positive;
    for b_n−1=1 the number stored in the register is negative.
In this case, the leftmost bit is called the sign bit.
As for placing the bits of an unsigned binary number in a register, it is a general rule that
– the digit having the highest positional value of the number is stored in the leftmost or MSB position in the register (i.e. which has the highest sequence number, e.g. b_n−1), and accordingly,
– the digit having the lowest positional value of the number is stored in the rightmost or LSB position in the register (i.e. which has the lowest sequence number, e.g. b₀).
If we store a given number in a register, the digits of the number can be assigned to the bits of the register in different ways (depending on the type and size of the represented number, the used encoding etc.). Accordingly, we can talk about the following coding or number representation methods:

direct coding of binary integers^⇒
two's complement representation of binary integers^⇒
binary coded decimal (BCD) representation of signed or unsigned integers^⇒
floating point representation of real numbers^⇒

(1) direct coding

Direct coding is used especially for representing non-negative (or unsigned) integers. In this case, the bits of the unsigned binary integer are stored in the usual order of their positional value in the one-bit storage units of the register (i.e. the highest positional value belongs to the MSB of the register, and the smallest positional value the the LSB, respectively). Since we only represent non-negative numbers in the case of direct coding, we do not need a sign bit.
In the case of direct coding, the smallest number that can be stored in an 8-bit register is 0000|0000₂=0₁₀, and the largest number is 1111|1111₂=255₁₀.

(2) two's complement representation of binary integers

Let's suppose we have an 'n'-bit register having the modulus m=2ⁿ and an integer between the range −m/2 and m/2−1. We can code the integer as follows:

the value of the sign bit should be 0 for non-negative numbers and 1 for negative numbers (so we can represent exactly the same number of non-negative and negative integers);
non-negative numbers are represented using direct coding;^⇒
negative numbers are represented as follows:

represent the absolute value of negative numbers using direct coding,
complement the value of the number thus obtained bit by bit, that is, replace 0 with 1 and replace 1 with 0 in each position (that is the so-called one's complement coding usually denoted by overline), and
add 1 in binary to the complemented number.

This is called two's complement coding.
For example, let's represent some numbers in an 8-bit register using two's complement coding (the subscript '2c' after the bit sequences denotes a number represented in two's complement code):

decimal value direct code decimal value two's complement code
0₁₀ 0000|0000₂
1₁₀ 0000|0001₂ −1₁₀ 1111|1111_2c
2₁₀ 0000|0010₂ −2₁₀ 1111|1110_2c
3₁₀ 0000|0011₂ −3₁₀ 1111|1101_2c
...
23₁₀ 0001|0111₂ −23₁₀ 1110|1001_2c
...
126₁₀ 0111|1110₂ −126₁₀ 1000|0010_2c
127₁₀ 0111|1111₂ −127₁₀ 1000|0001_2c
−128₁₀ 1000|0000_2c

For example, −23₁₀=1110|1001₂ because 0001|0111₂=1110|1000₂ (one's complement) and adding 1 in binary 1110|1000₂+1₂=1110|1001₂ is given.
Note that in two's complement code 127₁₀ is the largest positive number that can be represented, and −128₁₀ is the smallest negative number that can be represented.
Two important rules:

The absolute value of a negative number represented in two's complement code can be obtained using the same algorithm that was used when forming the two's complement code of a negative number (i.e. using one's complement coding and adding 1 in binary).

For example, in case w=1010|0110₂ the one's complement code is v=0101|1001₂, and adding 1 in binary we get v+1= 0101|1001₂+1₂= 0101|1010₂ thus |w|=90₁₀ is given (that is, w=−90₁₀ because the sign bit of 'w' is 1).

Subtraction of a non-negative number can be done by adding the number's two's complement code. When applying the rule, the possible carry formed after adding the digits with the highest positional value must be ignored.

For example, let us calculate the x=49₁₀−27₁₀ difference (which is, actually, a sum using two's complement coding).
Let v=27₁₀=0001|1011₂, then w=−27₁₀= 1110|0100₂+1₂= 1110|0101₂. Since 49₁₀=0011|0001₂ so the difference in question

x=49₁₀−27₁₀= 0011|0001₂+1110|0101₂= 1|0001|0110₂
Let us ignore the bit formed in the highest position value (i.e. the carry bit 1). Thus we get for the difference x=0001|0110₂= 22₁₀ which is apparently the correct value.

By representing negative integers in two's complement code, subtraction can be performed by addition.

decimal value	direct code		decimal value	two's complement code
0₁₀	0000\|0000₂
1₁₀	0000\|0001₂		−1₁₀	1111\|1111_2c
2₁₀	0000\|0010₂		−2₁₀	1111\|1110_2c
3₁₀	0000\|0011₂		−3₁₀	1111\|1101_2c
		...
23₁₀	0001\|0111₂		−23₁₀	1110\|1001_2c
		...
126₁₀	0111\|1110₂		−126₁₀	1000\|0010_2c
127₁₀	0111\|1111₂		−127₁₀	1000\|0001_2c
			−128₁₀	1000\|0000_2c

(3) binary coded decimal (BCD) representation of signed or unsigned integers

BCD number representation encodes decimal integers by specifying the decimal digits as 4-bit binary numbers. For example, the decimal integer 123₁₀ can be represented

as an unsigned packed BCD string 00000001 00100011,
as a signed packed BCD string 00010010 00111100,
as an unsigned unpacked BCD string FFFF0001 FFFF0010 FFFF0011,
or as a signed unpacked BCD string FFFF0001 FFFF0010 11000011.

There are two types of BCD number representation:

In the case of packed BCD every decimal digit is represented in 4 bits (i.e. in one tetrad or "nibble"), and the 4-bit groups of bits follow each other in decreasing order (i.e. from left to right) according to the positional value of the represented decimal digits. As a result, two decimal digits can be represented on one byte.
In the case of unpacked BCD we add a 4-bit group of bits to each tetrad from the left completing it to a whole byte (i.e. to 8 bits); the upper 4 bits are called zone bits, and the lower 4 bits represent a decimal digit (as in the case of packed BCD representation). As a result, only one decimal digit can be represented on one byte.

In the case of packed BCD number representation, usually two digits are represented on one byte (the digit with a higher positional value is stored in the "upper" 4 bits or tetrad, while the digit with a lower positional value is stored in the "lower" 4 bits or tetrad of the byte). In case of a signed number representation, the lower 4 bits of the last byte are used to represent the sign of the number (e.g. 1100 for the plus sign or 1011 for the minus sign, see later). In digital computers usually all data are stored in bytes or the multiples thereof (e.g. because the smallest accessible unit of the computer memory is a byte). Therefore, if the number of tetrads is odd, then the packed BCD code (or string) is completed from the left with a tetrad containing a "leading" 0 (i.e. a sequence of four 0 bits).
In the case of unpacked BCD number representation, one decimal digit is represented in one byte:
– On the "upper" 4 bits (the so-called zone bits) a predetermined bit sequence is stored (this can be e.g. 0000 or FFFF); an exception may be the zone bit of the last (or rightmost) byte, which contains the code of the sign in the case of a signed number representation (see later).
– A decimal digit is stored in binary form on the "lower" 4 bits or tetrads.
In the case of signed unpacked BCD representation, the sign of the number is located in the "upper" 4 bits of the byte containing the last digit, instead of the zone bits of the last byte. The plus or minus sign is encoded as a 4-bit represented hexadecimal digit:

the plus (+) sign corresponds to A, C, E or F;
the minus (−) sign corresponds to B or D.

If the number is stored in memory, the digit(s) with the highest positional value will be at the lowest memory address ("big-endian order"). (This rule is followed when storing the characters of a string or the elements of an array in memory.)

(4) floating-point number representation

In the case of floating-point number representation, real numbers (either integers or fractions) are given in normalized form, and they are encoded with a given precision. The real number 'x' to be encoded has the general form
x = s*m*2^k
where 's' indicates the plus or minus sign of the number (s=±1), 'm' is the so-called mantissa (m∈ℝ), and 'k' is the exponent (k∈ℤ).
The number of the digits of the mantissa determines the accuracy of the representation, and the exponent determines the order of magnitude of the number that can be represented (cf. Nyakóné Juhász 2011: 21).
The floating-point representation of real numbers is usually

32 bit long for single-precision numbers, and
64 bit long for double-precision numbers.

In the following, we will deal with single-precision, 32-bit floating-point number representation. The specification is based on the IEEE 754 standard published in the eighties by the Institute of Electrical and Electronics Engineers (IEEE) (cf. Nyakóné Juhász 2011: 21-22).
If we represent a floating-point number with single precision in 32 bits, then
– the sign of the number is given in the leftmost one bit in the usual way (i.e. as a sign bit, see before),
– the exponent is given in the next 8 bits in excess-127 notation,
– and the mantissa is represented in fixed-point notation on the remaining 23 bits.
The format of the 32-bit single-precision floating-point representation of real numbers is as follows:

b b b ... b b b b b b b ... b b b
sign bit
encoded exponent (exp, 8 bit)
encoded mantissa (frac, 23 bit)

We shall denote
– the real number to be represented by 'x';
– the exponent of the normal form by 'k', and the encoded value of the exponent by exp (which is stored in the 8 bits reserved for it in the single-precision format shown above);
– the mantissa of the normal form by 'm', and the encoded value of the mantissa by frac (which is stored in the 23 bits reserved for it in the single-precision format shown above).
We shall distinguish three different cases:
(1) "normal" case:

2⁻¹²⁶≤|x|<2¹²⁸ ⇒ −126≤k<128
exp=k+127 ⇒ 1≤exp<255
1≤m<2
frac=m−1 ⇒ 0≤frac<1

the value of the mantissa and its encoded value 'frac' can be expressed as a binary fraction in the form
m=1.b₁...b₂₃
frac=0.b₁...b₂₃
where b_i denotes the binary digit having the positional value 2⁻ⁱ (1≤i≤23)

the smallest number to be represented in this case is |x|=2⁻¹²⁶ (where exp=1 and frac=0)

In normal case for the floating-point number 'x' to be represented
    |x|≥2⁻¹²⁶≈1.17549⁻³⁸ and
    |x|<2¹²⁸≈3.40282⁺³⁸
occurs.

(2) the case of "very small" numbers (close to or equal to zero):

0≤|x|<2⁻¹²⁶ ⇒ k=−126
exp=k+126 ⇒ exp=0
0≤m<1
frac=m ⇒ 0≤frac<1

the value of the mantissa and its encoded value 'frac' can be expressed as a binary fraction in the form
m=0.b₁...b₂₃
frac=0.b₁...b₂₃
where b_i denotes the binary digit having the positional value 2⁻ⁱ (1≤i≤23)

the largest number to be represented in this case is very close to |x|≈2⁻¹²⁶ (where exp=0 and frac=0.1111...)
the smallest number to be represented in this case is |x|=0 (where exp=0 and frac=0)

(3) the case of overflow: the absolute value of the numbers is "too" large (and therefore they cannot be represented as floating-point numbers)

2¹²⁸≤|x| ⇒ 128≤k (with 1≤m<2, as occurs in normal case)
exp=255 (i.e. the value of the exponent represented in 8 bits is 11111111 in binary)
both the actual value and the represented value of the mantissa can be arbitrary (in this case we do not take it into account)

In case of overflow, the displayed bit sequence is not interpreted as a number (regardless of the value of the mantissa), but rather as plus or minus infinity depending on the sign bit (±∞). The usual notation for the overflow is NaN ("not a number").

Example 1 (cf. Nyakóné Juhász 2011: 22): Consider the following 32-bit sequence of bits that defines a single-precision floating-point number:
    x=1 10000111 10100000000000000000000₂
Let's determine the corresponding real number in the decimal number system!
Based on the normal case (1)
– since the sign bit is 1, therefore 'x' is negative;
– exp=1000|0111₂=135₁₀ ⇒ k=exp−127=8;
– m=1.101000...₂, therefore
    m=1+1/2+1/8=8/8+5/8=13/8
occurs.
Since 2⁸=256, so the real number we are looking for is
x=−13/8*2⁸=−13/8*256=−416

Example 2: Consider the following 32-bit sequence of bits that defines a single-precision floating-point number:
    x=0 00000000 10100000000000000000000₂
Let's determine the corresponding (approximate) real number that corresponds the above sequence of bits!
Based on case (2)
– since the sign bit is 0, therefore 'x' is positive;
– exp=0000|0000₂=0₁₀ ⇒ k=exp−126=−126;
– m=0.101000...₂ (the mantissa in case (2) begins with 0.), therefore
    m=1/2+1/8=5/8
occurs.
So the real number we are looking for is
x=5/8*2⁻¹²⁶≈7.3468...10⁻³⁹

Example 3: Consider the following real number:
    x=7.5₁₀
Let's determine the bits that the floating-point representation of the number consists of.
The floating-point representation of the number clearly corresponds to the normal case^⇒ because x≫2⁻¹²⁶ holds.

the number is positive, so its sign bit is s=0
now let's determine the normalized form^⇒ of x=7.5 in base 2:

divide x=7.5 by 2 until we get a number between 1 and (less, than) 2 (note: if 'x' were less than 1, we would not divide, but multiply by 2)
since x/4=7.5/4=1.875 and 4=2², the normalized form is x=1.875*2²

since k=2, the characteristic 'k' can be represented by exp=k+127=129, so the binary form of the exponent is exp=129₁₀=1000|0001₂
since m=1.875, the representation of the mantissza 'm' can be obtained by converting the decimal fraction frac=0.875 to binary fraction; after some calculations^⇒ frac=0.875₁₀=0.111₂ holds

Based on the above calculations, the floating point representation of x=7.5 is
    x= 0 10000001 11100000000000000000000

b	b	b
sign bit
	encoded exponent (exp, 8 bit)
		encoded mantissa (frac, 23 bit)

Algorithms related to number systems and data representation