Computers use patterns of binary values to represent absolutely everything (including the numbers and characters to graphics and sounds in computer games). It’s very important to know how exactly how many bits we need to use to make a complex enough pattern of ones and zeroes for our needs.
Storing information as patterns of bits
Here is a challenge. Your task is to design a pattern of ones and zeroes that can be used to represent each of the 26 different moves a particular robot can carry out.
Perhaps a good way to do this would be to use the value zero to represent “Stop”, one for “Forward slowly”, two for “Forward at medium speed” and so on.
If we did this then we might end up with something like this :
- Stop : 0 (zero)
- Forward slow: 1 (one)
- Forward medium: 10 (two)
- Forward fast: 11 (three)
- Forward full speed: 100 (four) …
- …and so on …
- Turn left 90 degrees : 1001 (nine)
- Small jump : 10100 (twenty)
- High jump : 11001 (twenty five)
Lets imagine we decided to tell the robot to:
Go forward slowly, turn left 90 and then high jump.
This would translate to: 1100111001
Now we have a problem, is the first instruction “Go forward slowly” or “Go forward fast”!
There is no obvious way to tell if the robot should look at just the first bit, the first two bits or more.
This will never work.
A solution could be to give each instruction a fixed number of bits, that way the robot will know exactly where the bit pattern for each instruction starts and ends.
Computers have limited memory so we need to make sure that we give each pattern exactly enough bits for every possible value but no more. Efficiency is extremely important!
How many is “just right”?
We can calculate the number of available bits we need so that there will be enough possible patterns of ones and zeroes to represent all of the values that we need.
A good way to understand how to do this is to think about how it works in our own decimal number system and then apply the idea to binary instead.
Number patterns
If we have only one bit available then we can only make two very simple patterns. These are:
- 0
- 1
With two bits we can make four slightly more complex patterns. These patterns are:
- 00
- 01
- 10
- 11
With three bits we can create eight patterns:
- 000
- 001
- 010
- 011
- 100
- 101
- 110
- 111
It is possible to calculate how many patterns there will be using the formula:
Number of possible bit patterns = 2 n
Where n is the number of bits.
For example, with 32 bits it is possible to create 232 different patterns, or 4,294,967,296 (a little more than four and a quarter billion different patterns)
If necessary, we can work backwards as well. In the original example our robot needed 26 different bit patterns to represent all 26 commands it understands.
- 24 gives sixteen, this is not enough patterns.
- 25 gives thirty-two, slightly more than we need.
So our robot would need to use patterns of five bits to represent all of it’s commands and it would leave us with a few left over (perhaps we could use those for some upgrades at some future point).
Finally, we can also use this method to easily calculate the highest possible value we can make with a given number of bits.
Consider three bits. The lowest number value is zero (000). If there are eight patterns possible using three bits and one of those patterns is zero then the highest number value that can be made is one less than the number of patterns
Highest possible value = The number of possible patterns – 1
Highest possible value = 2 n -1
For example, the highest value that can be made using 32 bits is:
232 -1 = 4,294,967,295