LeetCode 405: Convert a Number to Hexadecimal

Problem Restatement

We are given a 32-bit signed integer num.

We must return its hexadecimal representation as a lowercase string.

The hexadecimal digits are:

0 1 2 3 4 5 6 7 8 9 a b c d e f

We must not use built-in conversion functions such as:

hex()

Negative numbers use two’s complement representation.

If the number is 0, return:

"0"

Input and Output

Example function shape:

def toHex(num: int) -> str:
    ...

Examples

For:

num = 26

The answer is:

"1a"

because:

26 = 1 * 16 + 10

and hexadecimal digit 10 is:

a

Another example:

num = -1

The answer is:

"ffffffff"

because a 32-bit signed integer stores -1 as all binary bits equal to 1.

First Thought: Repeated Division

For positive numbers, we can repeatedly divide by 16.

At each step:

1. Take the remainder.
2. Convert it into a hexadecimal digit.
3. Divide the number by 16.
4. Reverse the collected digits at the end.

For example:

26 % 16 = 10 -> a
26 // 16 = 1

1 % 16 = 1 -> 1

Reading backward gives:

1a

This works for positive numbers.

The main challenge is handling negative numbers correctly.

Key Insight

Computers store signed integers using two’s complement representation.

In a 32-bit system:

-1

is stored as:

11111111111111111111111111111111

Every hexadecimal digit represents exactly 4 binary bits.

So 32 bits become:

8 hexadecimal digits

The easiest approach is to treat the number as an unsigned 32-bit integer.

We can do that using:

num & 0xffffffff

This keeps only the lowest 32 bits.

For example:

-1 & 0xffffffff

becomes:

4294967295

whose hexadecimal form is:

ffffffff

Algorithm

If num is 0, return "0".

Otherwise:

1. Convert the number into a 32-bit unsigned value using:

num &= 0xffffffff

2. Repeatedly:
   • Take the last 4 bits using:

num & 15

• Convert that value into a hexadecimal digit.
• Shift the number right by 4 bits.

3. Reverse the collected digits.
4. Return the result.

Correctness

Each hexadecimal digit represents exactly 4 binary bits.

The expression:

num & 15

extracts the lowest 4 bits because:

15 = 1111₂

Those 4 bits correspond exactly to one hexadecimal digit.

After extracting the current hexadecimal digit, the algorithm shifts the number right by 4 bits:

num >>= 4

This removes the processed digit and moves the next hexadecimal digit into the lowest 4-bit position.

The algorithm repeats until all nonzero bits have been processed.

For negative numbers, the expression:

num & 0xffffffff

converts the value into its 32-bit two’s complement unsigned representation. Therefore, the algorithm processes exactly the same bit pattern stored by a 32-bit signed integer.

Because the algorithm extracts hexadecimal digits from least significant to most significant and reverses them at the end, the returned string is the correct hexadecimal representation.

Complexity

Even though we use a loop, the number of iterations is bounded by 8.

Implementation

class Solution:
    def toHex(self, num: int) -> str:
        if num == 0:
            return "0"

        digits = "0123456789abcdef"
        result = []

        num &= 0xffffffff

        while num:
            result.append(digits[num & 15])
            num >>= 4

        return "".join(reversed(result))

Code Explanation

We first handle the special case:

if num == 0:
    return "0"

Then we prepare the hexadecimal digit table:

digits = "0123456789abcdef"

The index inside this string is the numeric hexadecimal value.

For example:

digits[10]

returns:

"a"

We convert the number into its 32-bit unsigned representation:

num &= 0xffffffff

Then we repeatedly extract the lowest 4 bits:

num & 15

This gives a value between 0 and 15.

We convert that value into a hexadecimal character:

digits[num & 15]

Then we remove those bits:

num >>= 4

The digits are collected from right to left, so we reverse them at the end:

"".join(reversed(result))

Testing

def test_to_hex():
    s = Solution()

    assert s.toHex(26) == "1a"
    assert s.toHex(0) == "0"
    assert s.toHex(16) == "10"
    assert s.toHex(255) == "ff"
    assert s.toHex(-1) == "ffffffff"
    assert s.toHex(-2) == "fffffffe"
    assert s.toHex(2147483647) == "7fffffff"
    assert s.toHex(-2147483648) == "80000000"

    print("all tests passed")

Test Notes