Converting from decimal to octal or hexadecimal

It turns out that when you wish to convert from decimal to octal or hexadecimal, there is a very easy formula that you can use. I'll give you the one for octal, and let you puzzle out the hexadecimal version (which may come quite naturally to some of you).

To convert from octal to hexadecimal, all you need to do is group the binary digits into pairs of three and convert each one into the corresponding octal number. For instance, given the binary number 010011110, you would group 011 and 110 together. 010 is 2, 011 is 3 and 110 is 6. So the octal number is 0236.

So why exactly does this work? Well, let's take a look at what 011110 looks like:

  0 * 28

  1 * 27

  0 * 26

  0 * 25

+ 1 * 24

+ 1 * 23

+ 1 * 22

+ 1 * 21

+ 0 * 20

That's actually the same as

  0 * 22 * 26

+ 1 * 21 * 26

+ 0 * 20 * 26

+ 0 * 22 * 23

+ 1 * 21 * 23

+ 1 * 20 * 23

+ 1 * 22 * 20

+ 1 * 21 * 20

+ 0 * 20 * 20

Whoa! First, notice that the far right column is actually turning into powers of 8! 23 is 8, and 26 is 64! So this means for each group of three digits, we have the base increasing by a factor of 8. Moreover, look at the right hand column. It can sum up to at most 7 (since 20 + 21 + 22 = 1 + 2 + 4 and the binary digit just decides whether each power of two is included into the sum or not). That's exactly the same as having eight digits, 0 through 7, and once we sum them all together, we multiply the sum by a power of eight. That's just the same as making each group of three binary digits an octal digit!

A lot of computer science is about efficiency. For instance, one frequently used mechanism for measuring the theoretical speed of algorithms is Big-O notation. What most people don't realize, however, is that often there is a trade-off between speed and memory: or, as I like to call it, space and time.

Think of space efficiency and time efficiency as two opposite ends on a band (a continuum). Every point in between the two ends has a certain time and space efficiency. The more time efficiency you have, the less space efficiency you have, and vice versa. The picture below illustrates this in a simple fashion: