Computer, do this.

My thoughts, ideas and processes with computing

Decimal to Hexadecimal

Originally posted: Tue 15th Jan 2019

Last updated: Tue 15th Jan 2019

As a bit of fun on a Saturday afternoon I've created a small program to convert a decimal number to hexadecimal (base 10 to base 16).

What is hexadecimal?

So base 10 is the decimal numbers we all use day to day.

Here is 0 to 15:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15...]

Base 16 is hexadecimal, mostly commonly used (for me at least) in CSS for web development. If I wanted to change to colour of something to white I might use:

color: #fff;

or to make something black:

color: #000;

Here is 0 to 15 again but this time in hexadecimal:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F]

So loosely speaking, this is Cascading style sheet's (CSS) way of saying colour this element's pixels the defined colour mixture in RGB (red, green, blue)*. Using the example from before;

"FFF" is saying use the colour mixture of 15, 15, 15 for these pixels. Since we are working in base 16; 0 to F is 16 values long (go ahead, count them above). 15 is the highest possible value in base hexadecimal for a single component and so what it is really saying is colour these pixels with 100% of each colour (red, green, blue). This equates to white. "000" similarly is 0% of each colour; black.

So for a very stark red I could use "F00", a green "0F0", a blue "00F".

*Commonly there are two components for each colour and sometimes one or two components for alpha (transparency) but I'll ignore those for simplicity.

Algorithm

Before I'd decided which language to use I needed to understand the algorithm so I noted down the general method to take a number and convert it from decimal to hexadecimal. I know there are more efficient algorithms which can even convert from any base to another (I've seen them), but I wanted to write a short program to test my abilities.

Here are my initial notes;

Given a number in decimal.

  1. using integer division, divide the number by 16
    1. store the remainder as a component of the hexadecimal result
    2. if the result is 0:
      1. return the hexadecimal result
    3. else:
      1. go back to step 1 with the result as the number

A prime example of an algorithm which could benefit from recursion I thought.

Converting 10 to 15 as letters

I also noted that is the remainder was greater than 9, it would need converting to the corresponding letter. (Remember 10 in hex is 'A' or 'a').

I remembered that the ASCII number for 'A' is 65, 'B' is 66, 'C' is 67 etc. Therefore I devised a method for the conversion of components greater than 9 to the right letter in hex;

  1. if remainder is greater than 9:
    1. set the remainder to itself plus 55
    2. convert the remainder to the ASCII character at it's value

To demonstrate this; given the number 12, I want to end up with 'A' so: 12 + 55 = 67, the character at ASCII(67) is 'C'. Correct result!

Pre-tests

I did a few calculations on paper to test my algorithm;

32 decimal as hex gave me #20
35 decimal as hex gave me #23
1526 decimal as hex gave me #5F6

A Python implementation

So to cut to the chase, I decided to code this in python as a quick exercise and you can see the code below.

def to_hex(d):
global hex
    if (d == 0):
 ##base case 
       pass    
else:        
res = d // 16       
 rem = d % 16       
 if (rem > 9):  
          rem = chr(rem + 55)   
     hex.insert(0, rem)       
 to_hex(res)

Update: Conversion to Other Bases

As I thought about the possibility of other algorithms to convert decimals to other bases I was intrigued that the base is used when converting to base 16:

res = d // 16
rem = d % 16

If I were to convert a number to base 2 (binary), would it simply be a case of changing the two numbers here to 2? Lets try.

Lets do an easy number to convert: 15

d = 15
#recursion 1
res = d // 2
 ## 15 // 2 = 7
rem = d % 2
## 15 % 2 = 1, so we have our first binary digit (1)
#recursion 2
res = d // 2 
 ## 7 // 2 = 3
rem = d % 2
 ## 7 % 2 = 1, Now we have our second binary digit (11)
#recursion 3
res = d // 2
 ## 3 // 2 = 1
rem = d % 2
## 3 % 2 = 1, our third binary digit (111)
#recursion 4
res = d // 2
 ## 1 // 2 = 0
rem = d % 2
## 1 % 2 = 1, our fourth binary digit (1111)
#recursion 5 d is now 0 so we stop with the result: 1111

So now we have what looks like a binary number, lets just check it is 15 by converting 1111 back to decimal:

Decimal     8        4        2        1
Binary      1        1        1        1
8 + 4 + 2 + 1 = 15

Adding a few 0's to the nibble to make it a full byte: 0000 1111 = 15

So it would appear to work. More checks would be needed before modifying my function but it would be a relatively simple case of introducing a new variable parameter called base which would be used to make the conversion.