1.4: Data types, data structures and algorithms:
Data types and data structures:
A variable's data type determines the values that the variable can store and the operations
that can be performed on it. For example, an integer is a whole number, which can be
added, subtracted, multiplied, or divided.
● An integer is an example of a primitive data type, as it can contain only one
value. Other examples of primitive data types are real (fractional numbers),
Boolean (true or false values), and character. Although a string is a collection of
characters, it is usually classified as a primitive data type.
● A composite or compound data type is built by combining primitive data types. An
example of a composite or compound data type is a record or a class.
● A data structure is a collection of data that is organised to allow efficient
processing. For example, the contents of an array can be sorted using a wide
range of sorting algorithms. Different data structures lend themselves to different
applications. Some data structures are highly specialised to specific tasks.
● An abstract data type is a conceptual model that describes how data is organised
and which operations can be carried out on the data (e.g. insert, delete) from the
perspective of an end user who does not need to know how this is implemented.
There are often many ways to implement an abstract data type, depending on the
programming language being used.
Sign and magnitude:
● We can make positive binary numbers into negative numbers by changing the
MSB from a 0 to a 1.
● When the MSB is changed to 1 to represent a negative number, the MSB becomes
what we call a ‘sign bit’ - meaning it no longer represents a weighted value. For
example, if an 8 bit binary number is made negative with the sign and magnitude
method, the MSB no longer represents 128. This means that the largest positive
number that can be stored is 127 rather than 255 and the smallest would be -127.
Two’s complement:
● The bits are checked from the least significant bit (the furthest right bit) to the MSB
of the binary representing the positive version of the number. For every 0, the 0 is
copied and kept the same. When a 1 is encountered, the 1 is copied and kept the
same but every bit after that is copied to be the opposite. This is because when we
convert the number to a negative number, the MSB’s value of 128 becomes -128.
Addition and subtraction of binary integers:
● Unsigned integers have positive values by definition, while signed integers can be
positive or negative.
● Addition:
○ Binary integers are aligned and added:
■ 0+0=0
■ 1 + 1 = 0 remainder 1
■ 1+0=1
■ 1 + 1 + 1 = 1 remainder 1
● Subtraction:
○ Same as addition but the second binary integer should be odd (converted
, using two’s complement).
Represent positive integers in hexadecimal:
● The hexadecimal digits range from 0-9 and then 10-15 where they are represented
by letters. E.g: 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F
● Binary and Hexadecimal:
○ Divide the binary digits so it is a series of 4 digits. Find the value of the 4
digits in denary and then the value in hexadecimal. E.g: 01101100 = 0110,
1100 = 6, 12 = 6C.
● Hexadecimal and denary:
○ Hexadecimal is in base 16 where binary is base 2 and denary is base 10.
○ E.g: 6C in denary will be (6 * 16) + (12 * 1) = 108
Floating point representation:
● Binary floating point numbers are expressed in the form mantissa x 2^exponent.
Normally, the mantissa is 8 digits and the exponent is 4 digits but this can vary.
● Two’s complement representation is used for the mantissa/exponent:
● Floating point binary to denary:
○ Using the place values above, you can determine that the mantissa value is
-0.625 and that the exponent is 2. Since the formula is mantissa x
2^exponent, the denary value is -0.625 x 2^2 = -2.5.
● Normalisation of floating point numbers:
○ To normalise a floating point binary number, you need to check whether the
number is positive or negative by checking the sign of the mantissa, and
act as follows:
■ If the number is positive, you need to move through the mantissa
from left to right until you find the first bit whose value is 1. The
binary point will be positioned immediately in front of this bit. A
normalised positive number always starts as 0.1
■ If the number is negative, you need to move through the mantissa
from left to right until you find the first bit whose value is 0. The
binary point will be positioned immediately in front of this bit. A
normalised negative number always starts as 1.0
○ After you move the binary point, you must adjust the exponent so that the
value of the number remains the same.
■ Moving the binary point one place to the right is equal to a left shift
that multiplies the number by 2. Hence, you need to compensate by
dividing the number by 2, which you can do by reducing the
exponent by 1.
■ Moving the binary point one place to the left is equal to a right shift
that divides the number by 2. Hence, you need to compensate by
multiplying the number by 2, which you can do by increasing the
exponent by 1.
● Adding and subtracting floating point numbers:
Data types and data structures:
A variable's data type determines the values that the variable can store and the operations
that can be performed on it. For example, an integer is a whole number, which can be
added, subtracted, multiplied, or divided.
● An integer is an example of a primitive data type, as it can contain only one
value. Other examples of primitive data types are real (fractional numbers),
Boolean (true or false values), and character. Although a string is a collection of
characters, it is usually classified as a primitive data type.
● A composite or compound data type is built by combining primitive data types. An
example of a composite or compound data type is a record or a class.
● A data structure is a collection of data that is organised to allow efficient
processing. For example, the contents of an array can be sorted using a wide
range of sorting algorithms. Different data structures lend themselves to different
applications. Some data structures are highly specialised to specific tasks.
● An abstract data type is a conceptual model that describes how data is organised
and which operations can be carried out on the data (e.g. insert, delete) from the
perspective of an end user who does not need to know how this is implemented.
There are often many ways to implement an abstract data type, depending on the
programming language being used.
Sign and magnitude:
● We can make positive binary numbers into negative numbers by changing the
MSB from a 0 to a 1.
● When the MSB is changed to 1 to represent a negative number, the MSB becomes
what we call a ‘sign bit’ - meaning it no longer represents a weighted value. For
example, if an 8 bit binary number is made negative with the sign and magnitude
method, the MSB no longer represents 128. This means that the largest positive
number that can be stored is 127 rather than 255 and the smallest would be -127.
Two’s complement:
● The bits are checked from the least significant bit (the furthest right bit) to the MSB
of the binary representing the positive version of the number. For every 0, the 0 is
copied and kept the same. When a 1 is encountered, the 1 is copied and kept the
same but every bit after that is copied to be the opposite. This is because when we
convert the number to a negative number, the MSB’s value of 128 becomes -128.
Addition and subtraction of binary integers:
● Unsigned integers have positive values by definition, while signed integers can be
positive or negative.
● Addition:
○ Binary integers are aligned and added:
■ 0+0=0
■ 1 + 1 = 0 remainder 1
■ 1+0=1
■ 1 + 1 + 1 = 1 remainder 1
● Subtraction:
○ Same as addition but the second binary integer should be odd (converted
, using two’s complement).
Represent positive integers in hexadecimal:
● The hexadecimal digits range from 0-9 and then 10-15 where they are represented
by letters. E.g: 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F
● Binary and Hexadecimal:
○ Divide the binary digits so it is a series of 4 digits. Find the value of the 4
digits in denary and then the value in hexadecimal. E.g: 01101100 = 0110,
1100 = 6, 12 = 6C.
● Hexadecimal and denary:
○ Hexadecimal is in base 16 where binary is base 2 and denary is base 10.
○ E.g: 6C in denary will be (6 * 16) + (12 * 1) = 108
Floating point representation:
● Binary floating point numbers are expressed in the form mantissa x 2^exponent.
Normally, the mantissa is 8 digits and the exponent is 4 digits but this can vary.
● Two’s complement representation is used for the mantissa/exponent:
● Floating point binary to denary:
○ Using the place values above, you can determine that the mantissa value is
-0.625 and that the exponent is 2. Since the formula is mantissa x
2^exponent, the denary value is -0.625 x 2^2 = -2.5.
● Normalisation of floating point numbers:
○ To normalise a floating point binary number, you need to check whether the
number is positive or negative by checking the sign of the mantissa, and
act as follows:
■ If the number is positive, you need to move through the mantissa
from left to right until you find the first bit whose value is 1. The
binary point will be positioned immediately in front of this bit. A
normalised positive number always starts as 0.1
■ If the number is negative, you need to move through the mantissa
from left to right until you find the first bit whose value is 0. The
binary point will be positioned immediately in front of this bit. A
normalised negative number always starts as 1.0
○ After you move the binary point, you must adjust the exponent so that the
value of the number remains the same.
■ Moving the binary point one place to the right is equal to a left shift
that multiplies the number by 2. Hence, you need to compensate by
dividing the number by 2, which you can do by reducing the
exponent by 1.
■ Moving the binary point one place to the left is equal to a right shift
that divides the number by 2. Hence, you need to compensate by
multiplying the number by 2, which you can do by increasing the
exponent by 1.
● Adding and subtracting floating point numbers:
