Today’s post is a little different. It is not about Ethereum, Blockchain or anything remotely modern, but rather about a fundamental of programming: the representation of numbers inside a computer.
This has been in the back of my head for some time, since I had a conversation with a friend programmer when comparing programming techniques. He was telling me how nowadays he did not feel the need to understand hexadecimal or binary numbers, it seems programmers no longer come across that in their education. I don’t need much of an excuse to write about topics I like, and numerical bases are one such. So I took him at his word and decided to write this post and reminisce a little about when I was introduced to them.
Back in the 80s, I was introduced to programming with the ZX Spectrum, and with its limited memory (48 Kb of RAM), the word of the day was how to make programs as small as possible. Not readable, nor maintainable: just small, so that they would fit in the computer’s memory.
There were several tricks programmers employed (my favourite was how Elite encoded 8 galaxies of several planets and their statistics in a decoder of of the output of a pseudo-random number generator). But the essentials were how to manipulate bits individually and make every bit of each byte work to the full. If you were in the habit of reading computer magazines, you’d pretty quickly get famin baseiliar with the first 16 or so powers of two, and several notable multiples, and also be fluent with binary and hexadecimal numbers.
Base 10
Starting at the base, let’s look at the western number system. We only use 10 digits which represent the quantities ‘zero’ to ‘nine’. To represent larger values, we use the fact that our numerical system is positional, unlike for example Roman Numerals. This means that the value of a symbol in a number depends on its position. It’s not a great secret that an integer number can be decomposed in a product of the face-value of a symbol times the value of its position, like this:
1472 = 1 x 1000 + 4 x 100 + 7 x 10 + 2 x 1
This representation holds the seed of all the secrets of numerical bases. We just have to look at it in a more compact, and formal, notation. Consider a number s, but let us look at it instead as an array, where each position holds a decimal digit. Plus, the digits are numbered from 0 to m where the digit in position 0 is the rightmost digit of the number. For example:
s = 1472 s[3] = 1 --- 1 thousand --> 1 x 103 s[2] = 4 --- 4 hundred --> 4 x 102 s[1] = 7 --- 7 tens --> 7 x 101 s[0] = 2 --- 2 units --> 2 x 100
In general, we can write:
s = Σi=0..m s[i] x 10i
- There are a few ideas here that generalise for any numerical base:
- There can be a numerical base of any order that is an integer larger than 1.
- In base n you can use exactly n different symbols to represent quantities. Symbols are often called digits and where there are more than 10, these are usually represented by letters.
- Numerical bases are positional systems where the value of a number is the sum of the value of its digits multiplied by the value of their positions.
- The value of each position is a power of the base. The exponent is the index of this position, where 0 is given to the rightmost position.
- Any integer number can be represented in any numerical base.
- It is common to indicate the base in which a number is represented by a adding a small number to its right, for example
100(10)is a hundred, represented in base 10. - Arithmetic operations (addition, subtraction, multiplication and division) work the same way in any base, safe for the fact that tables for addition and multiplication are represented differently (and will require a different number of entries).
Binary (Base 2)
The most common bases when dealing with computers, besides base 10, are hexadecimal (base 16) and binary (base 2). In ‘ancient’ times, there was also octal (base 8), but nowadays I don’t see it used anywhere (except file permissions in Linux). In binary, we use only 2 digits, 0 and 1 and because of this numbers take more digits to represent than in base 10.
For example, the number 100(2) is represented in base 2, and does not represent the value one-hundred. What number is this in base 10?
Remember the expansion I gave above of 1472? I’ll do the same now for this, but remember this time we’re dealing with base 2. This gives us:
s = 100(2) s[2] = 1 --- 1 'hundred' --> 1 x 22 = 4 s[1] = 0 --- 0 'tens' --> 0 x 21 = 0 s[0] = 0 --- 0 units --> 0 x 20 = 0
We add these numbers together and get the result: 4.
Let’s try a bigger number:
s = 1000 1010 1101 1001(2) s[15] = 1: 1 x 32768 = 32768 s[14] = 0: 0 x 16384 = 0 s[13] = 0: 0 x 8192 = 0 s[12] = 0: 0 x 4096 = 0 s[11] = 1: 1 x 2048 = 2048 s[10] = 0: 0 x 1024 = 0 s[9] = 1: 1 x 512 = 512 s[8] = 0: 0 x 256 = 0 s[7] = 1: 1 x 128 = 128 s[6] = 1: 1 x 64 = 64 s[5] = 0: 0 x 32 = 0 s[4] = 1: 1 x 16 = 16 s[3] = 1: 1 x 8 = 8 s[2] = 0: 0 x 4 = 0 s[1] = 0: 0 x 2 = 0 s[0] = 1: 1 x 1 = 1 Total: 35545(10)
The revised operation tables are now:
+ | 0 | 1 ---+---+--- 0 | 0 | 1 ---+---+--- 1 | 1 |10
x | 0 | 1 ---+---+--- 0 | 0 | 0 ---+---+--- 1 | 0 | 1
And the way we do operations is the same:
1011 + 0010 = position 0: 0 + 1 = 1 position 1: 1 + 1 = 10, ie, 0 and carry 1. position 2: 0 + 0 + 1 (carry from previous position) = 1 position 3: 1 + 0 = 1 Result: 1101
Let’s verify the addition in decimal. The two terms are 11 and 2, and the result is 13, as expected.
For multiplication, once you are comfortable with addition you can use the exact same long multiplication algorithm.
Hexadecimal (Base 16)
Hexadecimal is more frequently used than binary, since binary numbers are unyieldy beyond a certain size. I can imagine people representing bytes in binary, but in practice there is a much better option: hexadecimal.
Hexadecimal is a good base because it is not too far off from 10, and generates numbers of comparable size, but can represent bytes and words measured in bytes more regularly than base 10. This is because hexadecimal has 16 symbols, and because of that each of them can be represented by exactly 4 bits. This means that all bytes can be represented by 2 hexadecimal digits, and anything taking more than that will also not fit in a single byte.
Base 10, on the other hand, does not have this property. All bytes can be represented in 3 or less digits, but the majority of 3-digit numbers are greater than what can fit in 1 byte. For example, 300 requires 9 bits to write in binary: 1 0010 1100.
Because we have 16 symbols in this base, the decimal digits are not enough, and we have to create 6 more symbols. It is conventional to use the letters a to f to represent the values 10 to 15. We can convert hexadecimal numbers to decimal in the same way as above, but now we use powers of 16. For example:
s = 1ea8(16) s[3] = 1 --- 1 x 163 = 1 x 4096 = 4096 s[2] = 14 --- 14 x 162 = 14 x 256 = 3584 s[1] = 10 --- 10 x 161 = 10 x 16 = 160 s[0] = 8 --- 8 x 160 = 8 x 1 = 8 Total: 7848
It is very easy to convert between hexadecimal and binary, in both directions. Each hex-digit corresponds to 4 bits and every 4 bits correspond to one hex-digit. The number I used above 1000 1010 1101 1001(2) can easily be converted to hexadecimal one 4-bit cluster at a time:
1000(2) = 8 = 8(16) 1010(2) = 10 = a(16) 1101(2) = 13 = d(16) 1001(2) = 9 = 9(16) Result: 8ad9
Likewise, the number 1ea8(16) can be converted to
1(16) = 10 = 0001(2) e(16) = 14 = 1110(2) a(16) = 10 = 1010(2) 8(16) = 8 = 1000(2) Result: 0001 1110 1010 1000
It is common to write hexadecimal in clusters of 2 symbols. This is because each two symbols are exactly one byte.
Hexadecimal numbers are often used to represent binary data in printable text. Because ASCII includes non-printable characters, when we want to serialise binary data (that is a sequence of bytes) you can’t just print them to paper or screen. Instead, you can print the bytes values. Hexadecimal is more apt for this than decimal because every byte will be neatly represented by 2 characters. Decimal, on the other hand, would require 3-character codes (with lots of leading zeroes).
An example of a hexadecimal string is the following (the address of the Crypto-Kitties token contract):
0x06012c8cf97bead5deae237070f9587f8e7a266d
This is one case where the hex string only serves as a convenient identifier and no one really cares what the value is. So why do I fret about converting from base 16 to 10 and vice-versa? Is that even needed today?
Yes. Even Etherscan is an example. You can inspect any transaction there, and see the input data and the output, but all the fields will be represented in hexadecimal. You will have to convert them to decimal before studying the transaction.
Converting from base 10
So far, I only showed how to read a number in any base back to base 10. But how do you do the opposite, from base 10 to any base?
There is a simple way, that proceeds by steps. Divide your number by the base. The remainder of the division gives you the rightmost digit in the new base. Then take the quotient and repeat the process, getting the second rightmost digit. Repeat again, and so on, until the remainder is 0.
Here is an example:
Convert 8000 to hexadecimal: 8000 = 16 x 500 + 0: 0 500 = 16 x 31 + 4: 4 31 = 16 x 1 + 15: f 1 = 16 x 0 + 1: 1 Result: 1f40(16)
The algorithm can be written this way in Python:
def hexdigit(d):
if d < 10:
return str(d)
else:
return chr(d + ord('a') - 10)
def convert(n,b):
d=[]
while n > 0:
d.append(n % b)
n = n // b
d.reverse()
print("".join([hexdigit(x) for x in d]))
There are more things to say about numerical bases, but I will leave that for a later post. I hope this one served as a reminder or an introduction into this topic.