C++ Types 2

Encoding Numbers

To start of with we will want to store numbers. Let’s assume we want to store unsigned integers. Believe it or not there are many ways of encoding unsigned integers into bits.

The simplest method I can imagine is the following, we could encode the number by the number of sequential 1 bits, e.g. 1 is 1, 11 is 2, 111 is 3, 1111 is 4 etc. Use 0 as a marker for the end of the number and we have 10 is 1, 1110 is 3 and 1111111110 is 9. You could represent any number using this scheme. The major disadvantage of this method is that the space used to represent the number is the same as the magnitude of the number. This means it will take 1 Megabit to represent the number 1048576. To resolve this we need to use a positional notation to represent a number.

Read the rest of this entry »