Convert a Number to Hexadecimal: Bit Masking

LeetCode Convert a Number to Hexadecimal (Problem 405) asks you to return the hexadecimal representation of a given integer. Positive numbers work the way you would expect: 26 becomes "1a". Negative numbers use two's complement, so -1 becomes "ffffffff". You cannot use any built-in library method that handles the conversion directly.

The approach: extract 4 bits at a time

The key insight is that each hexadecimal digit corresponds to exactly 4 binary bits. To convert an integer to hex, you repeatedly mask off the lowest 4 bits using & 0xf, map that value to the right hex character, and then right-shift the number by 4 positions to expose the next nibble.

For negative numbers, Python integers have arbitrary precision, so you first mask the input with 0xffffffff to force it into a 32-bit unsigned representation. This gives you the two's complement form automatically. After that, the same nibble extraction loop works for both positive and negative inputs.

The algorithm is:

1. Handle the special case where num is 0 (return "0" immediately)
2. If num is negative, mask it with 0xffffffff to get the 32-bit two's complement
3. While num is greater than 0, extract the lowest 4 bits with num & 0xf
4. Look up the corresponding hex character from "0123456789abcdef"
5. Right-shift num by 4 to move to the next nibble
6. Reverse the collected characters (since you built the string from least significant to most significant)

def to_hex(num: int) -> str:
    if num == 0:
        return "0"
    if num < 0:
        num += 2 ** 32
    hex_chars = "0123456789abcdef"
    result = []
    while num > 0:
        result.append(hex_chars[num & 0xf])
        num >>= 4
    return "".join(reversed(result))

Walkthrough: num = 26

Let's trace through the conversion of 26 to hexadecimal step by step. The binary representation of 26 is 00011010. We extract 4 bits at a time from the right.

After two iterations, num reaches 0 and the loop ends. The digits were collected in reverse order (['a', '1']), so reversing gives "1a".

Complexity

A 32-bit integer has at most 8 hex digits. The loop runs at most 8 times regardless of the input value. The output string is also at most 8 characters. Both time and space are constant.

The building blocks

Bit masking with & 0xf. The mask 0xf (binary 1111) isolates the lowest 4 bits of any integer. This is the same principle behind checking odd/even with & 1, but extended to grab a full nibble. You will see this pattern whenever you need to extract a fixed-width chunk of bits from a number.

Right-shifting by 4. After extracting the lowest nibble, num >>= 4 shifts the remaining bits down by 4 positions. The nibble you just read falls off the bottom, and the next nibble moves into the lowest position. This is the bitwise equivalent of integer division by 16.

Two's complement for negative numbers. Adding 2 ** 32 to a negative number (or equivalently masking with 0xffffffff) converts it to the unsigned 32-bit representation. In two's complement, -1 is represented as all 1-bits: 0xffffffff. This trick lets you handle negatives with the exact same extraction loop.

Edge cases

num = 0. The output is "0". Without the early return, the while loop would never execute (since 0 is not greater than 0), and you would return an empty string.

Negative numbers. For num = -1, adding 2 ** 32 gives 4294967295, which is 0xffffffff. The loop extracts eight f digits. Every negative 32-bit integer maps to a valid unsigned value this way.

num = -1 (all bits set). This is the extreme negative case. The two's complement is 0xffffffff, producing the maximum-length output of "ffffffff".

Large positive numbers. For num = 2147483647 (the maximum 32-bit signed positive integer), the hex representation is "7fffffff". The loop still runs at most 8 times.

From understanding to recall

The bit masking loop in this problem is one of the most reusable patterns in bit manipulation. You mask, you shift, you repeat. The same structure appears in problems like Reverse Bits, Number of 1 Bits, and any time you need to process an integer nibble by nibble or bit by bit.

What trips people up in interviews is not the concept but the details. Which mask do you use? How many bits do you shift? How do you handle negative numbers in Python where integers are not fixed-width? These are the things that need to be automatic, not puzzled out under pressure.

Spaced repetition locks in those details. You solve the problem once, then revisit it at increasing intervals. Each review takes less time because the pattern is already partially encoded in memory. After a few repetitions, you can write the nibble extraction loop without thinking about it.

Related posts

• Number of 1 Bits - Another bit manipulation problem using masking
• Reverse Bits - Bit-by-bit processing of a 32-bit integer
• Sum of Two Integers - Bit manipulation for arithmetic