Problem Description

This problem asks you to convert a 32-bit integer into its hexadecimal representation as a string.

The key requirements are:

1. Input: A 32-bit integer num (can be positive, negative, or zero)

2. Output: A string representing the hexadecimal value of the number

3. Special handling for negative numbers: Use two's complement representation. This means negative numbers should be treated as their unsigned 32-bit equivalent. For example, -1 in 32-bit two's complement is represented as 0xFFFFFFFF, which should return "ffffffff".

4. Format requirements:

   • All letters must be lowercase (a-f, not A-F)
   • No leading zeros (except when the number itself is 0, which should return "0")
   • Cannot use built-in library methods that directly convert to hexadecimal

The solution works by:

• Handling the special case of 0 directly
• For other numbers, iterating through 8 hexadecimal digits (32 bits ÷ 4 bits per hex digit = 8 digits)
• Extracting each 4-bit group using bit shifting and masking with 0xF (binary 1111)
• Converting each 4-bit value (0-15) to its corresponding hex character (0-9 or a-f)
• Building the result string while skipping leading zeros

The bit manipulation (num >> (4 * i)) & 0xF extracts the i-th hexadecimal digit from the right, where each hex digit represents 4 bits of the original number.

Intuition

The key insight is recognizing that hexadecimal is base-16, where each digit represents exactly 4 bits of binary data. This natural alignment between hexadecimal and binary makes bit manipulation the perfect tool for this conversion.

Think about how we normally extract digits from a decimal number - we might use division and modulo operations. For hexadecimal, we can do something similar but with bit operations since we're working in powers of 2.

Since each hex digit represents 4 bits, a 32-bit integer contains exactly 8 hex digits (32 ÷ 4 = 8). We can extract each group of 4 bits one at a time by:

1. Shifting the bits to position the desired 4-bit group at the rightmost position
2. Masking with 0xF (binary 1111) to isolate just those 4 bits

For example, to get the second hex digit from the right, we shift right by 4 bits and mask: (num >> 4) & 0xF.

The beauty of this approach is that it naturally handles negative numbers correctly. In two's complement representation, negative numbers have their high bits set to 1. When we treat the 32-bit pattern as unsigned and extract 4-bit chunks, we automatically get the correct hexadecimal representation without any special negative number handling.

Starting from the most significant digit (leftmost) and working right allows us to easily skip leading zeros - we simply don't start adding characters to our result until we encounter the first non-zero digit. This is why the loop goes from i = 7 down to 0, processing from the most significant hex digit to the least significant.

The mapping from the extracted 4-bit value (0-15) to hex characters is straightforward using a lookup string '0123456789abcdef' where the index corresponds to the decimal value.

Solution Approach

Let's walk through the implementation step by step:

1. Handle the base case:

if num == 0:
    return '0'

If the input is 0, we immediately return '0' to avoid complications with leading zero handling.

2. Set up the hex character mapping:

chars = '0123456789abcdef'

This string serves as a lookup table where index i gives us the hexadecimal character for value i (0-15).

3. Initialize the result list:

s = []

We use a list to build our result string efficiently, as string concatenation in Python creates new string objects each time.

4. Extract hex digits from most significant to least significant:

for i in range(7, -1, -1):
    x = (num >> (4 * i)) & 0xF

• We iterate from i = 7 down to i = 0, processing 8 hex digits total
• For each iteration, 4 * i calculates how many bits to shift right
• When i = 7: shift right by 28 bits to get the most significant hex digit
• When i = 0: shift right by 0 bits to get the least significant hex digit
• The & 0xF operation masks the result to keep only the lowest 4 bits (values 0-15)

5. Skip leading zeros and build the result:

if s or x != 0:
    s.append(chars[x])

• The condition s or x != 0 ensures we:
  • Skip leading zeros (when s is empty and x is 0)
  • Include all digits once we've found the first non-zero digit (when s is non-empty)
  • This elegantly handles the leading zero requirement

6. Return the final string:

return ''.join(s)

Join all collected hex characters into a single string.

Example walkthrough with num = 26:

• Binary: 00000000 00000000 00000000 00011010
• Iteration i=7: (26 >> 28) & 0xF = 0 → skip (leading zero)
• Iteration i=6: (26 >> 24) & 0xF = 0 → skip (leading zero)
• ...continue skipping zeros...
• Iteration i=1: (26 >> 4) & 0xF = 1 → append '1'
• Iteration i=0: (26 >> 0) & 0xF = 10 → append 'a'
• Result: "1a"

For negative numbers like num = -1:

• In 32-bit two's complement: 11111111 11111111 11111111 11111111
• Each 4-bit group equals 1111 (15 in decimal, 'f' in hex)
• Result: "ffffffff"

The algorithm runs in O(1) time complexity since we always process exactly 8 hex digits, and O(1) space complexity for the result string.

Example Walkthrough

Let's walk through converting num = 170 to hexadecimal using our bit manipulation approach.

Step 1: Binary representation

• 170 in binary: 00000000 00000000 00000000 10101010
• Expected hex result: "aa" (since 10101010 = 0xAA)

Step 2: Initialize

• chars = '0123456789abcdef' (our lookup table)
• s = [] (empty result list)

Step 3: Extract each hex digit (from most to least significant)

• i = 7: (170 >> 28) & 0xF

  • Shift: 170 >> 28 = 0
  • Mask: 0 & 0xF = 0
  • Action: Skip (leading zero, s is empty)

• i = 6: (170 >> 24) & 0xF

  • Shift: 170 >> 24 = 0
  • Mask: 0 & 0xF = 0
  • Action: Skip (leading zero, s is empty)

• i = 5, 4, 3, 2: All produce 0

  • Action: Skip all (leading zeros)

• i = 1: (170 >> 4) & 0xF

  • Shift: 170 >> 4 = 10 (shifts out rightmost 4 bits: 1010)
  • Mask: 10 & 0xF = 10 (decimal)
  • Action: Append chars[10] = 'a' to s
  • s = ['a']

• i = 0: (170 >> 0) & 0xF

  • Shift: 170 >> 0 = 170 (no shift)
  • Mask: 170 & 0xF = 10 (keeps only last 4 bits: 1010)
  • Action: Append chars[10] = 'a' to s
  • s = ['a', 'a']

Step 4: Join and return

• ''.join(s) = "aa"

The algorithm correctly extracts the two hex digits A and A (lowercase as required) from the binary representation, skipping all leading zeros to produce the final result "aa".

Solution Implementation

Time and Space Complexity

Time Complexity: O(1)

The algorithm iterates through a fixed loop of 8 iterations (from i = 7 to i = 0). In each iteration, it performs constant-time operations:

• Right shift operation: num >> (4 * i) - O(1)
• Bitwise AND operation: & 0xF - O(1)
• Array/string indexing: chars[x] - O(1)
• List append operation: s.append() - O(1) amortized

Since the loop runs exactly 8 times regardless of the input value, the overall time complexity is O(8) = O(1).

Space Complexity: O(1)

The algorithm uses:

• A fixed string chars of length 16 - O(1)
• A list s that stores at most 8 characters (since we process 8 hexadecimal digits) - O(1)
• A few integer variables (i, x) - O(1)

The maximum space used is bounded by a constant (the output string can have at most 8 characters for a 32-bit integer), making the space complexity O(1).

Common Pitfalls

1. Incorrect Handling of Negative Numbers in Different Programming Languages

One of the most common pitfalls occurs when implementing this solution in languages that handle integer bit operations differently, particularly with negative numbers.

The Problem: In Python 3, integers have arbitrary precision, meaning negative numbers don't automatically wrap around to their 32-bit two's complement representation. When you perform bit operations on negative numbers in Python, they maintain their sign through an infinite series of leading 1s.

For example, in Python:

• -1 >> 4 results in -1 (not 0x0FFFFFFF as you might expect)
• The bit pattern extends infinitely: ...11111111111111111111111111111111

Why This Breaks:

# Incorrect approach that fails for negative numbers
def toHex_wrong(num):
    if num == 0:
        return '0'
  
    hex_chars = '0123456789abcdef'
    result = []
  
    # This will create an infinite loop for negative numbers!
    while num != 0:
        result.append(hex_chars[num & 0xF])
        num >>= 4  # For negative numbers, this never becomes 0
  
    return ''.join(reversed(result))

The Solution: The provided solution cleverly avoids this issue by:

1. Using a fixed loop of exactly 8 iterations (not a while loop)
2. Relying on Python's automatic handling of the & 0xF operation, which correctly extracts 4 bits regardless of sign

However, if you need to explicitly handle the two's complement conversion, you can:

# Alternative approach: Convert negative to unsigned 32-bit
if num < 0:
    num = (1 << 32) + num  # Convert to unsigned 32-bit representation

2. Off-by-One Errors in Bit Shifting

The Problem: It's easy to make mistakes with the bit shift calculations, especially when determining which bits to extract.

Common Mistake:

# Wrong: This extracts bits in the wrong order
for i in range(8):  # Going from 0 to 7
    x = (num >> (4 * i)) & 0xF  # Extracts from least to most significant
    if result or x != 0:
        result.append(hex_chars[x])
# This would produce "a1" instead of "1a" for num=26

The Solution: Always remember that for proper hexadecimal representation:

• We need to extract from most significant to least significant digit
• Use range(7, -1, -1) to iterate from 7 down to 0
• The shift amount should be 4 * i where larger i values correspond to more significant digits

3. Forgetting Edge Cases

The Problem: Failing to handle special cases properly, particularly:

• Zero (returning empty string or "00000000")
• Maximum negative number (-2^31)
• Small positive numbers (returning with leading zeros)

The Solution: Always include explicit handling:

# Correct: Handle zero explicitly
if num == 0:
    return '0'

# Correct: Skip leading zeros but include all digits once we start
if result or hex_digit_value != 0:
    result.append(hex_chars[hex_digit_value])