Data representation

Why computers use binary, and the number systems you need

Every form of data has to be converted to binary before a computer can process it. That is because the circuits inside a computer are built from transistors that behave like switches, and a switch has only two states: on or off. One switch holds one bit, so a bit is always either 1 (on) or 0 (off). Text, sound, images, video and even the instructions of a program are all stored as patterns of bits. The data is processed using logic gates and held in registers while it is being worked on.

There are three number systems you have to know. Denary is base 10 and uses the digits 0 to 9, and it is the system humans use. Binary is base 2 and uses only 0 and 1, and it is the system the computer uses. Hexadecimal is base 16 and uses 0 to 9 plus A to F, where A is 10, B is 11, C is 12, D is 13, E is 14 and F is 15. Hexadecimal is not used by the computer itself; it is a shorthand that makes binary easier for humans to read.

Hexadecimal is useful because exactly one hex digit represents four bits, so 8 bits become two hex digits and 16 bits become four. A value such as 1101 0111 0011 1010 is far easier to read, write down and check as D73A, and long strings of 1s and 0s are easily miscopied. That is why hexadecimal is used wherever addresses and codes are displayed: MAC addresses, IPv6 addresses, the memory addresses shown in error messages, and colour codes in web pages such as #FF8800.

Converting between denary, binary and hexadecimal

Denary to binary. Write out the place values 128, 64, 32, 16, 8, 4, 2, 1 and take the largest one that fits, then carry on with what is left. For 173: 128 fits, leaving 45; 64 does not fit; 32 fits, leaving 13; 16 does not fit; 8 fits, leaving 5; 4 fits, leaving 1; 2 does not fit; 1 fits. That gives 1010 1101. Check it by adding the place values of the 1s: 128 + 32 + 8 + 4 + 1 = 173.

Binary to denary. Add up the place values of every bit that is a 1. For 0010 1101 that is 32 + 8 + 4 + 1 = 45.

Binary to hexadecimal. Split the binary into groups of four bits, starting from the right, and convert each group on its own. 1010 1101 becomes 1010 and 1101; 1010 is 10, which is A, and 1101 is 13, which is D, so the answer is AD. If the number of bits is not a multiple of four, pad the left-hand group with zeros first.

Hexadecimal to binary. Replace each hex digit with its own four bits. 2D becomes 0010 for the 2 and 1101 for the D, so 0010 1101. Denary to hexadecimal. Either convert to binary first and group the bits in fours, or divide repeatedly by 16 and read the remainders: 173 ÷ 16 = 10 remainder 13, and 10 is A while 13 is D, so the answer is AD. Hexadecimal to denary. Multiply each digit by its place value: 2D -> (2 x 16) + (13 x 1) = 32 + 13 = 45.

Conversions in the exam can go in either direction and can involve values up to 16 bits, so a 16-bit binary value needs four hex digits.

Adding binary integers, and overflow

Binary addition follows four rules: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, and 1 + 1 = 0 carry 1. When three bits are added together, 1 + 1 + 1 = 1 carry 1. Work from the least significant bit on the right to the most significant bit on the left, carrying into the next column exactly as you do in denary addition.

Here is 0011 0110 (54) added to 0101 1010 (90). Working column by column and carrying where needed gives 1001 0000. Check it in denary: 54 + 90 = 144, and 1001 0000 is 128 + 16 = 144.

An overflow error occurs when the result of a calculation is larger than the largest value the register can hold. An 8-bit register holds any value from 0 to 255, so an overflow error occurs if the answer is greater than 255. A 16-bit register holds up to 65 535, so the same rule applies at a higher limit: a computer has a predefined limit on what it can represent or store, and an overflow error occurs when a value outside that limit should be returned.

Adding 1011 0100 (180) to 0110 1101 (109) gives 289, which is larger than 255. The addition produces a carry out of the most significant bit, but there is nowhere for it to go inside an 8-bit register, so it is lost. The register keeps only 0010 0001, which is 33, and that is completely wrong. The carry out of the most significant bit is the signal that an overflow has happened.

Logical shifts: multiplying and dividing by powers of two

A logical shift moves every bit in the register a set number of places to the left or to the right. In a logical left shift each bit moves one place to the left, a 0 is shifted in at the right-hand end, and any bits pushed off the left-hand end are lost. In a logical right shift each bit moves one place to the right, a 0 is shifted in at the left-hand end, and any bits pushed off the right-hand end are lost.

The effect on the value is predictable. A left shift multiplies the value by 2 for each place shifted, and a right shift divides it by 2 for each place shifted, throwing away any remainder. A multiple shift is just a repeated single shift.

For 0001 0110, which is 22: a left shift of 1 gives 0010 1100 (44); a left shift of 2 gives 0101 1000 (88), which is 22 x 4; a right shift of 1 gives 0000 1011 (11); and a right shift of 2 gives 0000 0101 (5), because 22 ÷ 4 is 5.5 and the 0.5 is lost when the last two bits are shifted off the end.

The danger is losing a significant bit. Left shifting 1100 0011 (195) by one place gives 1000 0110, which is 134, not 390: the 1 in the most significant bit has been shifted off the end and lost, so the doubling has not worked. A left shift only multiplies by 2 if no 1 is lost from the most significant bit, and a right shift only divides exactly if no 1 is lost from the least significant bit.

Two's complement: representing negative integers

Binary has no minus sign, so a computer stores negative integers using the two's complement system. The most significant bit becomes a sign bit: 0 means the value is positive and 1 means it is negative. Positive integers are written in the usual way, with a 0 in the most significant bit.

To write a negative number in 8-bit two's complement, write the positive value in 8-bit binary, invert every bit (change every 1 to a 0 and every 0 to a 1), then add 1. For -25: +25 is 0001 1001; inverting gives 1110 0110; adding 1 gives 1110 0111. So -25 is 1110 0111.

To convert a two's complement value back to denary, look at the sign bit. If it is 0 the value is positive and you simply add the place values. If it is 1 the value is negative: invert all the bits, add 1, and put a minus sign in front. For 1111 0000: the sign bit is 1, so the value is negative; inverting gives 0000 1111, which is 15, and adding 1 gives 16, so the value is -16.

Eight-bit two's complement covers -128 to +127. 1000 0000 is -128 and 0111 1111 is +127, so +128 and -129 cannot be stored in 8 bits. Negative values can also be added and subtracted directly without any special rules, which is one reason computers use two's complement rather than a separate sign bit.

Text, sound and images: how a computer stores them

Text is stored using a character set, which is an agreed list that gives every character a binary code. ASCII (American Standard Code for Information Interchange) was designed for English and originally used 7 bits, giving 128 characters: the letters, the digits, punctuation marks and some control codes. Because the same code is used by every device, text can be moved between systems and still be read correctly. Unicode was developed because ASCII cannot cover the characters of other languages, and it allows for a much greater range of characters and symbols, including different languages and emojis. Unicode needs more bits per character than ASCII, so a text file that uses Unicode is larger.

Sound is stored by sampling. A microphone turns the sound wave into an electrical signal, and the computer measures that signal at regular intervals and records each measurement as a binary number. The sample rate is the number of samples taken in a second, and the sample resolution is the number of bits used for each sample. Raising either one makes the recording a more accurate copy of the original sound wave, but also increases the file size.

Images are stored as a grid of pixels. Each pixel is given a binary value that represents its colour. The resolution of an image is the number of pixels in the image, and the colour depth is the number of bits used to represent each colour. A higher resolution means more detail, and a higher colour depth means more different colours can be shown, but both increase the file size.

Storage units, file sizes and compression

Data storage is measured in units that each hold a fixed number of the unit before them. A bit is one binary digit. A nibble is 4 bits and a byte is 8 bits, and each step up from a byte is 1024 of the previous unit: 1024 bytes in a kibibyte, 1024 kibibytes in a mebibyte, and so on up through gibibyte, tebibyte, pebibyte and exbibyte. Calculations must use 1024, not 1000.

To find the file size of an image, multiply the number of pixels by the colour depth: file size in bits = resolution x colour depth. For an image of 1024 x 768 pixels with a colour depth of 8 bits: 1024 x 768 = 786 432 pixels; 786 432 x 8 = 6 291 456 bits; ÷ 8 = 786 432 bytes; ÷ 1024 = 768 KiB.

To find the file size of a sound file, multiply the sample rate by the sample resolution by the length of the track in seconds: file size in bits = sample rate x sample resolution x length. For a track recorded at 8192 samples per second with a sample resolution of 16 bits and a length of 8 seconds: 8192 x 16 x 8 = 1 048 576 bits; ÷ 8 = 131 072 bytes; ÷ 1024 = 128 KiB. Always give the answer in the unit the question asks for.

Compression exists to reduce the size of a file. A smaller file needs less storage space, requires less bandwidth when it is sent and takes less time to transmit. Lossy compression reduces the file size by permanently removing data, for example by reducing the resolution or the colour depth of an image, or the sample rate or resolution of a sound, so the file can never be put back exactly as it was. Lossless compression reduces the file size without permanently losing any data, for example run length encoding (RLE), which stores a value once together with the number of times it repeats, so AAAAABBB becomes 5A3B. With lossless compression the original file can be recreated exactly.