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

```python
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:

```python
hex()
```

Negative numbers use two's complement representation.

If the number is `0`, return:

```python
"0"
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | A 32-bit signed integer `num` |
| Output | Hexadecimal string |
| Digits | Lowercase hexadecimal digits |
| Negative numbers | Use two's complement |
| Special case | `0` returns `"0"` |

Example function shape:

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

## Examples

For:

```python
num = 26
```

The answer is:

```python
"1a"
```

because:

```python
26 = 1 * 16 + 10
```

and hexadecimal digit `10` is:

```python
a
```

Another example:

```python
num = -1
```

The answer is:

```python
"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:

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

1 % 16 = 1 -> 1
```

Reading backward gives:

```python
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:

```python
-1
```

is stored as:

```python
11111111111111111111111111111111
```

Every hexadecimal digit represents exactly 4 binary bits.

So 32 bits become:

```python
8 hexadecimal digits
```

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

We can do that using:

```python
num & 0xffffffff
```

This keeps only the lowest 32 bits.

For example:

```python
-1 & 0xffffffff
```

becomes:

```python
4294967295
```

whose hexadecimal form is:

```python
ffffffff
```

## Algorithm

If `num` is `0`, return `"0"`.

Otherwise:

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

```python
num &= 0xffffffff
```

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

```python
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:

```python
num & 15
```

extracts the lowest 4 bits because:

```python
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:

```python
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:

```python
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(1)` | A 32-bit integer has at most 8 hexadecimal digits |
| Space | `O(1)` | At most 8 characters are stored |

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

## Implementation

```python
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:

```python
if num == 0:
    return "0"
```

Then we prepare the hexadecimal digit table:

```python
digits = "0123456789abcdef"
```

The index inside this string is the numeric hexadecimal value.

For example:

```python
digits[10]
```

returns:

```python
"a"
```

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

```python
num &= 0xffffffff
```

Then we repeatedly extract the lowest 4 bits:

```python
num & 15
```

This gives a value between `0` and `15`.

We convert that value into a hexadecimal character:

```python
digits[num & 15]
```

Then we remove those bits:

```python
num >>= 4
```

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

```python
"".join(reversed(result))
```

## Testing

```python
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

| Test | Why |
|---|---|
| `26` | Basic positive number |
| `0` | Special case |
| `16` | Exact power of 16 |
| `255` | Multiple hexadecimal digits |
| `-1` | All bits set |
| `-2` | Negative two's complement case |
| `2147483647` | Largest 32-bit signed positive integer |
| `-2147483648` | Smallest 32-bit signed integer |