Convert Number to Hexadecimal, solving a short Facebook Interview question

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

   +--------------------------------------------------------------------+
   | 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.

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

Handling Positive Numbers

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

    let res = "";

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

Handling Negative Integers

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.

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.

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

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.

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.

Smarter way

For this we need to understand two basic concepts of bit manipulation.

   & 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 :

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 :

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