405. Convert a Number to Hexadecimal

Given an integer, write an algorithm to convert it to hexadecimal. For negative integer, two’s complement method is used.

Note:

1. All letters in hexadecimal (a-f) must be in lowercase.

2. The hexadecimal string must not contain extra leading 0s. If the number is zero, it is represented by a single zero character '0'; otherwise, the first character in the hexadecimal string will not be the zero character.

3. The given number is guaranteed to fit within the range of a 32-bit signed integer.

4. You must not use any method provided by the library which converts/formats the number to hex directly.

Example 1:

Input:
26

Output:
"1a"

Example 2:

Input:
-1

Output:
"ffffffff"

要限制長度是因為signed int如果right shift，開頭的bit不會自動變成0，如果本來是negative number，那麼開頭補進來的數就會是1。但while loop的終止條件是num變成0，所以需要特別限制res的長度。

string toHex(int num) { // time: O(1); space: O(1)
    string hex = "0123456789abcdef";
    if (num == 0) return "0";
    string res;
    while (num && res.length() < 8) {
        res = hex[num & 0xf] + res;
        num >>= 4;
    }
    return res;
}

如果用unsigned int就沒right shift後補進來的開頭bits的問題。

string toHex(int num) { // time: O(1); space: O(1)
    string hex = "0123456789abcdef";
    if (num == 0) return "0";
    string res;
    unsigned int n = num;
    while (n) {
        res = hex[n & 0xf] + res;
        n >>= 4;
    }
    return res;
}