Convert Number to Hexadecimal, solving a short Facebook Interview question
Tags: computerscience, javascript, career, tutorial
Published: 2020-06-06 14:17:21

Question : Given an integer, write an algorithm to convert it to hexadecimal. 

Lets tart with what's hexadecimal numbers ?

Hexadecimal number are the number represented in base 16, it consists of 16 symbols

```javascript 
   +--------------------------------------------------------------------+
   | Decimal     : 0  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15 |
   | Hexadecimal : 0  1  2  3  4  5  6  7  8  9   A   B   C   D   E   F |
   +--------------------------------------------------------------------+ 
```

To make our lives easier, let's create an array that will store the hexadecimal values to its corresponding decimal index. 

```javascript
   let map = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'];
```

<h3> Handling Positive Numbers </h3>

Handling positive numbers is easy. It's a 3 step operation and it's intuitive :

Step 1 : store the result of num%16 
Step 2 : perfrom num/16
Step 3 : perform step 1,2 till num > 0 

```javascript
    let res = "";
    
    while(num > 0) {
        let digit = num % 16;
        res = arr[digit] + res;
        num = Math.floor(num / 16);
    }
```

<h3> Handling Negative Integers </h3> 
Handling negative integers becomes a bit tricky, since we can't write -#3AC to represent negative hexadecimal numbers, so let's a dive deeper and represent numbers in their binary forms. 

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/liouwl2hulpzi3puyade.gif)

And since any number is bolied down to binary 0's and 1's, we face the same issue of representing negative numbers in binary format since a computer won't understand -0010. 

So to solve this issue, negative numbers are represented by setting Most Significant Bit to 1.

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/jb3acn07jj7hbcg6v46t.png)

So how can we use this two key information to solve our problem ? 
On closer look we see this : 

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/mh0l9feg03jd7ks75cxm.png)

Since an integer is 32-bit, which is further broken down to parts of 4-bit, and binary representation of numbers 8 - 16 have 1 set as their Most Significant Bit and 8 - F represent those numbers, so we could say that 8 - F range could be used to represent negative numbers. 

So a hex number #FFFFF63C represents a negative number.

Whenever we come across a number < 0, we add 2^32, to it to convert into a format which could be mapped with hexadecimal mappings.

```javascript
var toHex = function(num) {
    let map = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'];
    
    if (num == 0) return "0";
    
    if (num < 0) {
        num += Math.pow(2,32);
    }
    let res = "";
    
    while(num > 0) {
        let digit = num % 16;
        res = map[digit] + res;
        num = Math.floor(num / 16);
    }
    return res;
};
```

This was a normal way to do it, now let's see an even smarter way of achieving the same which will definitely impress your interviewer. 

<h3> Smarter way </h3>
For this we need to understand two basic concepts of bit manipulation.

```javascript 
   & operator
   1 & 1 = 1
   0 & 0 = 0
   0 & 1 = 0
   1 & 0 = 0

   >>> right shit operator
   shifts bit's to right
   5 >>> 1 = 101 >>> 1 = 10 = 2. 
   Here the number is being shifted right once. 
```

So if we perform -14&15 , -14&15 we get, &15 because we want to convert it to hex and F equals 15 : 

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/dazcjpt6e3f13slr6qcz.png)

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/tunu550qgcflwd6ztuik.png)

Based on this we can say that &15 will convert negative decimal in relevant hexadecimal negative value while preserving positive decimal value.

Now all the basics out of the way, this technique consists of two steps. 

Step 1 > res += map[num&15]
Step 2 > num>>>4. 
Step 3 Repeat step 1 & 2 till num != 0

We performing step 2 is similar to diving num/16. Since 15 is 1111 ie 4 bits in binary form, we preform the "&" operation and remove those 4 bits.  

Converting it to code : 
```javascript
var toHex = function(num) {
    if (num == 0) return '0';
    let map = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'];
    let result = '';
    while (num != 0) {
        let c = map[num & 15]; // map last 4 bits to a hex digit
        result = c + result;
        num = num >> 4;
    }
    return result;
};
```
I hope you liked my article :) 

github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/decimalToHex.js