When we want to represent or communicate information in a computer system, we need to make decisions about how that information should be encoded.

One option that we will look at in detail is using binary. However, in principle we are not limited using binary to encode information. For instance, we encode data in a set of traffic lights or in the spins of subatomic particles. This is part of a branch of mathematics and computer science called information theory.

Our goal in this lecture is to be able to design simple encodings for arbitrary data. For example, in the lecture notes you will see the example of encoding binary files as twitter posts containing only emojis. On the way, we will learn about:

• How computers represent data
• Binary, octal, and hexadecimal number systems

Encode numbers and data with binary and other number systems
1. Interpret a number in any base written using positional notation
2. Understand binary can represent text and data
3. Encode ASCII-encoded text as binary
4. Apply logarithms to find the inverse of exponentiation
5. Calculate how many digits are needed to write a given number
6. Calculate how many numbers can be stored with a given number of digits
Manipulate positive and negative numbers written in binary
1. Interpret binary numbers encoded using sign and magnitude
2. Find the Ones complement of a binary number
3. Find the Twos complement of a binary number
4. Perform binary addition
5. Perform binary subtraction
6. Perform binary multiplication
Convert numbers between different bases
1. Convert from any base to decimal
2. Convert from decimal to any base
3. Convert directly between bases that are powers of two

Binary is a way of writing numbers using only ones and zeroes. Everyone knows that computers store data in binary.

Of course, in reality computers store data in the physical properties of objects: hard drives, solid state drives, or even tape drives. In a hard drive, areas of a metal disk are magnetised or demagnetised to encode data, which gives two states that can be reliably differentiated. Binary is a way of abstracting this two-state physical system.

The smallest unit of information, a 0 or 1 is called a bit. Eight of these together is called a byte. The number of bits of information in a system provides an upper bound on the unique number of states that it can represent.

We can think of systems of all kinds as storing information, and they need not include only two states. However, the unit used to quantify information in any system is the bit. For instance, in physics one can calculate the information density of the universe to be 1 bit per plank area (\( A_p = 10^{-70}m^2 \)) of the boundary of the universe, leading to a theoretical maximum on the amount of information the universe can contain. To simulate the observable universe would require a computer to store approximately \( 10^{10^{123}} \) bits of information.

However, we will constrain ourselves to much more practical scales. How can we use binary to encode information in our computing systems? The most straightforward way to use binary is to represent numbers, and this is what we will look at first. The rules by which binary does this are the same as many number systems: positional notation.

To be able to encode binary or text data as emojis we will first address smaller problems which will let us build the necessary knowledge.

We will begin by learning about binary and the way binary numbers are represented using positional notation. We will learn how to encode text and other data in binary.

We will then extend this to representing data in other number systems such as octal and hexadecimal. As part of this we will learn to convert between different number systems.

When we want to work with numbers we need to write them down somehow. The Romans did this using Roman numerals: I, II, III, IV, etc. However, we need a form of notation that also lets us efficiently express large numbers such as $24,674,349$. The system that we use was first invented by the ancient Babylonians, and is called positional notation.

To start with, we need a set of symbols (digits) to use to represent numbers. The decimal system has 10 symbols (called base 10) \( \{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 \} \). Binary uses two symbols (base 2) \( \{ 0, 1 \} \).

When we write a number, we write an ordered string of digits. Each digit contributes to the overall value of the number. The value each digit contributes is dependant upon three things:

• the digit used (e.g. 0, 1, 2, etc.)
• the position of that (e.g. rightmost, second from right, third from right, etc.)
• the base (here 10, as we are working in decimal)

We sum the values to find the value of the number overall. For example, the number 423 in decimal (base 10) is equivalent to $4 \times 100 + 2 \times 10 + 3$. We can also write this:

Which is four hundred and twenty three.

Each digit is multiplied by a positional value or 'weight' that depends upon its position in the number. This positional value is the base (here 10) raised to the power of the position of the digit, counting from the right. The right most digit has position 0, so has weight $10^0 = 1$. This position is also called the 'units'; position 1 (with weight $10^1$) is also called the 'tens'; and so on.

Binary is also expressed using the rules of positional notation. However, in binary, rather than the positional values being increasing powers of 10 as in decimal, they are increasing powers of 2.

If it is not obvious why, consider that a one digit binary number can store only two values 0 and 1. By the time we need another digit the next number to represent is 2. Similarly, if we have two digits, they can represent $ 2 \times 2 $ values (0-3), so the next number we need to represent is $4$. Three digits can represent $2 \times 2 \times 2$ values, so the next number to represent is $8$, and so on in increasing powers of 2.

When writing numbers that are not in base 10, we will often notate them as $(n)_b$, where $n$ is the number and $b$ is the base.

It is helpful to have memorised the first several powers of 2 starting from $2^0: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, \dots$. These are the positional values in binary and knowing them off-by-heart will allow you to read binary numbers in your head.

How do we store data in binary? For instance, say I have a text file containing the text:

How would this be stored in binary?

For most data, such as text, it is common to group bits together into groups of fixed length. For instance, bits might be grouped into bytes (8 bits) or words (commonly 32 bits or 64 bits, depending on processor architecture). Primitive data types in most programming languages have a fixed length. For example, in C a char is 8 bits and an int is 32 bits.

If we group bits into groups of 7 bits, we can work with our data as an array or list of numbers between 0 and 127. This is because 0000000, or 0 is the smallest number that can be stored and 1111111, or 127 is the largest number.

Let us associate each of these 128 values with a character. There is a standard way of doing this called ASCII. ASCII includes all English alphabet letters (upper and lower case), numbers, and several non-printing characters such as line breaks. We can encode text in ASCII by storing each character as the associated ASCII value in binary.

This 7-bit standard is extended in 8-bit ASCII, which uses 8 bits per character (256 possible symbols). Here, by adding one bit (the bit with positional value $2^7$) we gain an additional $2^7 = 128$ possible characters.

Another extension of ASCII, UTF-16, uses 16 bits per character, and so can represent \( 2^{16} = 65536 \) symbols.

01110100 01101000 01100101 00100000 01110001 01110101 01101001 01100011 01101011 00100000 01100010 01110010 01101111 01110111 01101110 00100000 01100110 01101111 01111000 00100000 01101010 01110101 01101101 01110000 01110011 00100000 01101111 01110110 01100101 01110010 00100000 01110100 01101000 01100101 00100000 01101100 01100001 01111010 01111001 00100000 01100100 01101111 01100111

This lets us encode text into binary. However, say we want to encode text in a different way - say using emojis? The next thing we need to know is how to represent numbers and data in other number systems, which we will be able to generalise to novel encoding systems.

Now that we have seen how to use encode positive and negative numbers in binary, we will take a look at what we can do with these numbers.

To be able to add binary numbers, we need to be able to add together three bits: one from each number, and a carry bit. We start with the least significant bit of each number to add and our carry bit is 0. The sum is a single bit; any overflow goes into the carry bit.

1. Add lowest pair of bits
2. Determine sum and carry
3. From then on, add each pair of bits with previous carry
4. Final carry is overflow

This is how addition works in a digital circuit. A full adder is a circuit used to add two bits of data together. It takes in two bits to add and a carry bit and returns a sum bit and a carry bit. A half adder is the same, but does not take in a carry bit. To add two 8 bit numbers together we need 1 half adder and 8 full adders. The table below shows the truth table for a full adder. The truth table for a half adder is the same as the top half of the table, but it does not take a carry bit input.

For example, to add $0001$ and $1011$, we first add $1$ and $1$, for a sum of $0$ and a carry of $1$. We then move to the next column. We add $0$ and $1$ and our carry bit ($1$), for a sum of $0$ and a carry of $1$. We then add $0$ and $0$ and the carry bit ($1$), for a sum of $1$ and a carry of $0$. We then add $0$ and $1$ and the carry $0$ for a sum of $1$ and a carry of $0$.

  0001
+ 1011
------
  1100

To subtract a number, e.g. $a$, we can add its additive inverse, i.e. $-x$. When we represent negative numbers using twos complement, we can perform subtraction using the same algorithm as addition. However, if we represent negative numbers in a different way, we need to use a different algorithm for subtraction.

When we are using twos complement, to do $a - b$ we can flip all of the bits of $b$, add 1 (i.e. find its twos complement), and then find $a+b$ using the method described above for binary addition.

Binary multiplication is addition with a series of shifts. Imagine that we were performing it as a long-form multiplication. Multiply each digit in the bottom number by the top number, and write the answers in a column. Whenever the digit we are multiplying is not the rightmost (least significant bit), we must shift all bits in our answer left by the position of this digit. Once we've multiplied the top number by each digit in the bottom number, we add up the columns to get our answer.

   101
x   10
------
   000
+ 1010
------
  1010

In the example above, the line $000$ is obtained by multiplying the digit $0$ by $101$. The line $1010$ is obtained by multiplying the digit $1$ by $101$ and then shifting all bits left by $1$, because our digit $1$ is really a $10$.

If you have done any digital image editing or web development, you will be familiar with colours expressed as hexadecimal strings. For example, in the colour picker below, the colour is represented in hexadecimal.

A hex colour can be read in three parts. The first two digits give the red component, the second two are the blue component, and the the third two are the green component.

Hexadecimal (also called base 16) uses 16 symbols. We count 0 to 9 and then continue counting on the letters A (representing 10) to F (representing 15). The 16 symbols used in hexadecimal are:

Positional notation can work with any base. Octal, base 8 is another commonly used base. Base 1, unary, is possible so long as numbers can be of varying length.

Any other base could be devised, though if the base is higher than 10 it would be necessary to decide on what symbols to use after 9, as is the case with hexadecimal.

Let's say we want to devise a way of storing numbers using a given set of symbols. How many numbers could we store with a given number of characters? How many characters would we need to store a given number?

For example, say a URL shortening service like Bitly wants to encode a number in a URL. They want to use the fewest characters they can to improve efficiency. However, they are restricted with what characters URLs are allowed to contain. How do they decide on the optimal encoding?

To start with, lets refresh our intuition about multiplication. If I have a grid of 5 rows and 5 columns, I have $5 \times 5 = 25$ squares. If I have two digits and each digit take $5$ values, there are $5 \times 5 = 25$ pairs of values, or 25 unique 2-digit numbers.

In a base $b$ number, if we have $2$ digits, there are $b^2$ unique strings of digits and thus $b^2$ numbers can be represented. If we had 3 digits, $b^3$ numbers can be represented, and so on.

We could assign these unique values to any 'state' in a system, be that a numerical value or not. With 2 bits of information we can distinguish 4 different states. If we roll a four sided dice and look at the number, we have learned 2 bits of information.

If we decide to use these unique values to represent numbers starting from 0, the highest number we get to will be $b^n -1$. Thus the highest number a base $n$ number of $n$ digits can store under positional notation is $b^n-1$

We can now find out what number of bits a given number requires. However, what if we want to reverse the question: how many bits we need to store a given number? What if we want to store $x$ unique values, how many digits do we need?

We found the number of unique values for a given number of digits using exponentiation. The inverse of this is the logarithm. The logarithm is a mathematical function that, for a particular base, tells you how the 'order of magnitude' of a number, or the number of digits it contains. Logarithms are commonly performed to base 2, base 10, or base $e$ (a constant called Euler's number, this log is also called the natural log). The logarithm of $a$ to the base $b$ is written:

Explore the interactive graph below. This graph shows values up to $log_b a = 4$. Start by exploring base 10. See how the number of digits in $a$ corresponds to the value of \( log_{10} a \).

Logarithm is the inverse of exponentiation. Observe how taking the base $b$ logarithm of both sides of the equation below cancels out the exponentiation:

(The notation $\lceil x \rceil$ means round $x$ up: you can't have half a digit!).

Computers store data in binary. We can think of this as just storing a great many binary numbers. These numbers have no context. They do not themselves tell us how they should be interpreted. Each time we read a string of bits, it is up to us (or up to the state of the program) how to interpret it.

In particular, when interpreting a number we need to know whether it is supposed to be a signed number (i.e. one that can represent negative values) or unsigned number (i.e. one that only stores non-negative numbers).

There is no universal way of indicating that one of our numbers is negative, or that a number should be interpreted as a signed number. We need to know in advance how to interpret a particular string of bits. For signed numbers, this means we need to know which representation has been used to encode it.

We might reason that a number is either positive or negative. This information is boolean (true or false) and thus we can represent it with a single bit. One approach to encoding negative numbers is therefore to reserve one of our bits as a sign bit (usually the first). The sign bit encodes whether the number is positive (0) or negative (1). Thus we might have the numbers:

This is equivalent to mapping the (unsigned) numbers in the range $128$ - $256$ to negative values.

Notice a curious and undesirable consequence: we have two distinct values for $0$: $-0$ and $+0$. This makes the representation inefficient. With 1 bit set aside for the sign bit, the magnitude of the number is stored with 7 bits. We can store a magnitude up to $2^7 = 127$. Thus we can store the range $-127$ to $127$, only 255 numbers. Yet we know that we should be able to store up to $2^8 = 256$ different values with 8 bits.

Additionally, we require a different algorithm to do addition and subtraction on sign-and-magnitude numbers than we do on unsigned numbers. However, despite these drawbacks, sign and magnitude representation is one of the methods commonly used in microprocessors, mostly for embedded devices.

What else can we do to a number except for flipping one of the bits to represent a signed or unsigned number? How about flipping all of the bits?

One's complement is a transformation used to represent a negative binary number by flipping every bit (i.e. every 0 becomes 1, every 1 becomes 0). For example, the one's complement of $(10101)_2$ is $(01010)_2$.

Notice that we can still check whether a number is negative by looking at the first bit. If the first bit is a 1, our number is negative.

Unfortunately, with this method we still have two zeroes: $(0000)_2$ and $(1111)_2$, thus just as with Sign and magnitude, this method is inefficient.

Two's complement is a superior way of encoding negative numbers in binary. We can understand twos complement as an operation that we perform upon a binary number: "flip each bit, and add one".

With two's complement we now only have a single value for zero, which is $(00000000)_2$. The representation is efficient as (in 8 bits) it makes use of all $2^8 =256$ unique values. We store numbers from $-127$ to $128$. 128 is stored as $(10000000)_2$ (for which the two's complement is $(10000000)_2$)

It's little use devising an encoding if we are unable to convert data into it. To start with the simplest case, we have already seen how to convert from any base to decimal. To convert from base $n$ to decimal, we multiply each digit by its positional value, which is $b^n$ for base $b$ and position $n$ (starting from 0 on the right).

For example, we can convert $1110$ from binary into decimal as follows:

To convert from decimal to any base $b$, we repeatedly divide our number by $b$, finding the remainder at each step.

Let us consider the binary case first, as this is the easiest to understand.

128 ÷ 2 = 64, Remainder = 0
64 ÷ 2 = 32, Remainder = 0
32 ÷ 2 = 16, Remainder = 0
16 ÷ 2 = 8, Remainder = 0
8 ÷ 2 = 4, Remainder = 0
4 ÷ 2 = 2, Remainder = 0
2 ÷ 2 = 1, Remainder = 0
1 ÷ 2 = 0, Remainder = 1
Result: 10000000

To convert into binary we repeatedly divide by 2. The first time we do this, the remainder tells us whether 2 divides our number. If there is a remainder, the number was odd and the least significant digit must be 1. There is no other digit that can express this 'oddness' because all other digits are positive powers of 2, which are even.

Our division by 2 has now effectively shifted our binary number one place to the right, just like dividing by 10 shifts a decimal number one place to the right. So when we find the remainder after dividing by 2, we are asking if this new, shifted number is odd or even, and thus whether it must contain a 1. But because we have shifted one place to the right, we need to shift back so our remainder becomes our _second_ least significant digit.

This logic extends to other bases as well. Rather than the remainder or modulus operation telling us whether the number is odd, it tells us what is left over that any larger power of $b$ cannot represent. This must be in our least significant digit (as our least significant digit has a positional value of 1).

We can convert efficiently between bases that are powers of 2.

To convert from binary to hexadecimal, we can group bits into 4s, called quartets. We use four digits because to represent 1 hexadecimal digit (16 possible values) in binary requires 4 bits, as $\log_2 16 = 4$.

If we do not have enough binary bits to fill a quartet, we pad to the left with zeroes. Adding zeroes to the left of a number does not change its value.

Having grouped the bits into quartets, we convert each quartet into the corresponding hexadecimal digit.

Binary: 	11111111
Hexadecimal: 	FF

The first (lowest) four binary digits are encoding the same information as the first (lowest) hexadecimal digit, and so on for the second, third, and fourth, etc.

To go the other way, (i.e. from hexadecimal to binary) follow the process described above in reverse. Convert each hexadecimal digit into binary, and then concatenate them together. To convert between two bases that are both powers of 2, use binary as an intermediary.

To convert between binary and a base that is a powers of 2, we can group bits. First consider how many bits it requires to represent a single digit in the target base. For instance, in base 8, there are 8 different possible digits, thus we need 3 binary digits, because $2^3 = 8$. Starting with our binary number, we group the bits starting from the least significant bits. E.g. the three least significant bits become the first group, the next four least significant bits after these form the second group. If necessary, the binary number can be padded to the left with zeroes. Each group can then be convened into a single digit of the target base.