- Computers & Software
What is all this binary and hexadecimal and octal about anyway?
A bit of background.
At one time in my career, I needed to recruit many technical staff. One of the questions that I prepared asked to convert a binary number to octal. I was surprised to find that almost nobody could do it, and yet it is so simple.
Can you convert 110010011010010 to octal?
In your head?
If not, then read on...
We probably use base-10 because someone, sometime, somewhere used all ten fingers as a basic counting system and it developed from there. There is one Mexican language - according to the wikipedia article where the speakers used the spaces between their fingers as a base, and this led to an octal system in their language.
The truth is, we should have decided on base 12 (hexadecimal) because 12 has more factors, and it would make arithmetic easier since more divisions would become clean integer fractions. A base of 12 was not entirely neglected. We buy a dozen eggs, there are 12 inches in a foot, a gross is 12 x 12 = 144... But the Arabic base-10 system has over-powered any minor inroads for other bases... except BINARY!. What I will show is that binary and octal and hexadecimal are very tightly linked.
Unix and Linux permission bits are displayed on octal. Many codes are recorded in octal. Many early computer systems used octal because it was simple. They could make read-outs simply with only 8 required symbols and three binary inputs.
Here is a table which shows the equivalence.
Decimal Binary Octal 0 000 0 1 001 1 2 010 2 3 011 3 4 100 4 5 101 5 6 110 6 7 111 7
Before going further - let's examine base 10
Our familiar system uses 10 unique digits to represent number.
To make you think a little more about this, I am going to choose new symbols instead of the Arabic digits that we normally use. This will not change any of our arithmetic methods. It will just look strange. But work through the strangeness because it will help you understand what is really going on in other bases like hexadecimal.
What follows is a fictional account of how a number system might have evolved.
We need a symbol that represents a void or nothing, but preserves a spot where we could, if needed, apply another symbol that has weight (a value). In reality - the invention of zero was an earth moving theoretical advance. But in this story - (to make it short) we start with the world's greatest concept: nothing.
Let zero be represented by *
Farmer Bin has no sheep" Here is a record of that:
But one day, on his birthday, he is given a sheep, so he changes his records.
As time went on, he accumulated more sheep, until he had this many:
But this was getting ridiculous. He had a name for one sheep, which was "one", and he had a name for another one sheep which was "one one". This was okay when he added another: "one one one". But it soon got out of hand, and his records held little advantage over simply looking into the paddock, except perhaps to determine if one had died, been stole, or given birth.
What he decided to do is group them into "hands" like this:
And he made a new composite symbol using the placeholder * to represent it:
This, he called 'hand'. So now his records showed:
!* !* !* !* !* !* !* !* !* !* !!!!!!
This was much more compact and he grew rich with sheep on the back of this amazing counting system. But his hands got out of hand again:
!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!!! sheep was a little hard to comprehend.
Farmer Bin is a tidy fellow
Farmer Bin noted that he counted out hand hand hand hand and so on, but had some parts left over. For example, in one paddock, he had hand hand hand one one one one one one sheep.
He realized it would be very nice to have a symbol for one one and one for one one one... and so on.
Luckily, in his loft, he had an old QWERTY keyboard lying about and decided to use the following squiggles that were conveniently arranged across the top row of buttons. He did not know what they were, but figured it may be a common household item that he could use as a reference when talking with his friends:
one one @
one one one #
one one one one $
one one one one one %
one one one one one one ^
one one one one one one &
one one one one one one one (
one one one one one one one one )
He was a little miffed that * would have been in a good place to represent one one one one one one one one but he was so used to using * as zero, that he just could not get his head around changing it, or updating his 150 volumes of accounts.
Farmer Bin was a smart fellow though, and he quickly realised that
if one one one be represented by #, then
hand hand hand could be represented by #*
What he had done was place a power- or weighting of hand lots in the column to the left of *.
This was very concise, so he was able to record all four paddocks like this:
Paddock north: )% sheep
Paddock south: &$ sheep
Paddock west: #* sheep
Paddock east ^^ sheep.
Altogether, he had, um, a lot of sheep poo. Besides that, he had a total of
hand hand hand hand hand hand hand hand hand hand hand hand hand hand hand hand hand hand hand hand hand hand hand hand hand hand one one one one one.
But he noted that this was a long winded thing to say and created yet another group name so that hand hand hand hand hand hand hand hand hand hand was represented by another column - the third weighted column.
The total number of sheep that he owned was:
Taking a break one day, he pondered how he would continue, and came up with this idea.
The right most column is for lots of one. then one to the left of that he called a hand, and the the left of that he called a poo since there was so much of it. Farmer bin was having fun. He dreamed of many more columns, and names for them. He dreamed of a time when he would have ^%@#$ sheep.
and he named the columns, from right to left as:
one, hand, poo, truckload, ship.
He did this on the basis that each column to the left represented !* as many for each symbol as the one immediately to its right. Hence he had the one's column, the hand's column, the poo's column, the truckload's column, and the ship's column.
A ship was worth !* truckloads, and a truckload was worth !* poo, and a poo was worth !* hands, and a hand was worth !* ones.
But something was still not right. He had no sounds for these symbols. Farmer bin dreamed again and invented these names for his symbols:
! OH @ worm # fence $ cash % quiz ^ hat & squiggle ( opened ) closed * no
Using the rather common, but useless QWERTY artifact that most farmers seemed to keep in their loft, he taught this to all the other farmers, and one day made a big sale of squiggle-poo, hat-hand no-one sheep to farmer Dec.
How many is squiggle-poo, hat-hand no-one sheep?
It's just what it says. If I said to you, I have 760 sheep you could say, "Oh - seven hundred and 6 tens and no ones". The fact that we are lazy and say, "Seven hundred and sixty", is just a convenient short-hand.
In our system, and in Farmer Bin's system, we bunch things in groups of ten (ten is the same as Farmer bin's Oh-no = !* ) and every column to the left is ten times bigger.
In our system, with some slightly more advanced notation, we can write the weightings of each column in "powers" of ten:
... 10000 , 1000, 100, 10, 1
All we need to do is go abstract one more time, and use a little note above the digit to represent how many place-holding zeros are in each... like this:
...104 , 103 , 102 , 101 , 100 .
Note the really simple pattern. Maths is full of patterns. Look out for them because they usually mean something.
The BASE is 10 and the power keeps getting larger each time a column is added to the left.
It starts in the ones column as 100 because there are no zero place holders required here. These headings are called weightings because they weight the value of the symbol that you find in that column.
Hence, the number 760 REALLY means: (7 x 102) + (6 x 101) + (0 x 100)
Now you know everything you need to know to count in any base.
Lets do this for octal.We need eight symbols. Let's use eight of the ones that we already like:
the symbol 8 is not required, all we need to do is put a 1 in the eights' column:
But this looks like ten in decimal, so where there could be confusion, we write the base at the bottom like this
108 . which is pronounced one-oh-base 8. (We avoid saying 10 as ten because that is a term used in decimal).
Here are the weightings, written - this time for base eight.
It looks a little awkward - but it is correct. We have the ones column to the right, a column to the left of that for symbols that mean one one one one one one one one, and to the left of that a column for groups 108 times larger again and so on.
IN PRACTICE, we don't say 108 much, as it is OK to borrow the symbol 8 and use decimals for the weightings. In this case to mean one one one one one one one one. This gives us:
...84 , 83 , 82 , 81 , 80
As you probably know, 82 is 8 x 8 which is 6410, so we can call this the 6410's column if we wish to convert a number from octal to decimal.
The decimal weightings of the other columns are:
1 x 8 x 8 x 8 x 8 = 84 = 409610
1 x 8 x 8 x 8 = 83 = 51210
1 x 8 x 8 = 82 = 6410
1 x 8 = 81 = 810
1 = 80 = 110
To convert octal 712438 you would perform this sum (all in base 10):
7 x 4096 = 28672
1 x 512 = 512 +
2 x 64 = 128
4 x 8 = 32
3 x 1 = 3 ====== 2934710
Having done base 8 - let's look at binary a moment.
In binary - the BASE is decimal 2. So the weightings are:
20 = 1
21 = 2
22 = 4
23 = 8
24 = 16
25 = 32
26 = 64
27 = 128
28 = 256
29 = 512
210 = 1024
211 = 2048 212 = 4096
etc Note that ALL of the above numbers are decimal numbers.
Remember - we look for patterns in maths, and there is a pattern here that pops out nicely when we compare these weightings with the octal weightings.
20 = 1 This one is also an octal weighting. 21 = 2 22 = 4 23 = 8 This one is also an octal weighting. 24 = 16 25 = 32 26 = 64 This one is also an octal weighting. 27 = 128 28 = 256 29 = 512 This one is also an octal weighting. 210 = 1024 211 = 2048 212 = 4096 This one is also an octal weighting.
The pattern is that every THIRD binary weighting is also an octal weighting. This is because 23=8.
A binary number only needs two symbols. This is why it is good for computers and machines that need to represent number in a general way. When writing binary, we naturally choose 0 for the placeholder, and 1 for the symbol. Then a base-ten 2 in binary is 102 which is pronounced ONE-OH. The '1' is in the two's column, and the 0 is in the 1's column.
102 is shorthand for (1 x 2 ) + ( 0 x 1 ).
A longer example is:
1011011 which is shorthand for
(64 x 1) +(32 x 0) +(16 x 1) +(8 x 1) +(4 x 0) +(2 x 1) +(1 x 1)
= 64+16+8+2+1 = 9110
Finally - converting binary to octal.
We are going to convert 1011011 into octal.
Remember the pattern where we noted that 23=8 and the weightings matched in binary and octal every 3rd column? All we need to do is group the binary into bands of three. The number of permutations of a group of three binary numbers is 8. All we need to do to convert any binary number into octal is gather it up into bands of three and give it some symbols.
10110112 = (001) (011) (011)8 THIS IS ACTUALLY A CORRECT ANSWER... providing that we use the following set of symbols for our base 8. (Just like Farmer Bin has weird symbols and names for them - we can do the same for octal.)
(000) means the same as our decimal 0.
(001) means the same as our decimal 1
(010) means the same as our decimal 2
(011) means the same as our decimal 3 (100) means the same as our decimal 4
(101) means the same as our decimal 5
(110) means the same as our decimal 6
(111) means the same as our decimal 7
All we did was permute the three binary symbols to make 8 octal symbols. Sure, they are 4-part complicated messy symbols - but they are valid. Also valid are the decimal symbols on the right of the table above. We are happy to use decimal symbols for Octal anyway. I could have said, that the symbols we will use will be:
But why bother when 01234567 will do, and we are so used to them anyway?
Now we can convert binary to octal in one quick easy mental procedure. Here is a long example:
These thirty binary symbols:
= the ten "octal symbols":
110 010 011 000 110 100 010 010 001 100
But we can substitute the decimal symbols to make it shorter to write, and easier to speak:
And that's all there is to converting binary to octal.
But wait - there's more!
Hexadecimal is BASE 16. We need 16 symbols. The most natural ones to choose are:
0 1 2 3 4 5 6 7 8 9 A B C D E F
The weightings (in decimal) of each column are the powers of 16
...164 163 162 161 160
And a pattern is found because 24 = 16.
So all we need to do is group the binary digits into 4
0011 1001 0011 1000 1001 0011 0000 111116
( I had to tac on two zeros at the start to make up a group of four).
This, like in the OCTAL example is a valid answer, providing that we claim that each group of four is now a unique symbol. It's convenient that we made them out of the permutations of the binary group of four, but that's not of great importance. We can, again substitute each complex symbol for a more familiar symbol as in the following examples:
0011 = 3
1001 = 9
0011 = 3
1000 = 8
1001 = 9 1110 = E
0011 = 3
0000 = 0
1111 = F
All permutations for hexadecimal representation on a 7-segment display.
The tight relationship between octal and hexadecimal is important.
Binary is made of two symbols - 1 and 0.
But we could have used any two states. Here are some examples:
Flux density high, Flux density one slight bit higher.
X,x (That's big X, Little x)
When we build machines, Each column can be represented by a wire, and that wire needs to only show two states to be useful as a binary column. So we use voltage or current mostly. We can also use glass and use photons, or phases. Any physical phenomena may be used.
But it's very common to use one wire for one column. To make a display in OCTAL is dead easy, because all we need to do is energize some kind of light or pattern in a display that makes part of the pattern light up. The display that comes to mind is the 7-segment display. 7 lines have 8 states (including a state when all of them are not lit). This is ideal for octal.
If you arrange them like this:
| | -
| _ |
Then we can use one column of binary in groups of three and a bit of logic to light up all eight octal symbols that we need for a more compact display. Humans can't read binary digits easily, but octal is OK. Using the seven lights arranged as above, we can easily make the digits
1 2 3 4 5 6 7
It's only a short step to progress to hexadecimal, although a little harder to make
8 9 A B C D E F
as the D is confused with the zero and the 8 is confused with the B. So we create a lower case b and a lower case d.