Solution Explanation for Convert a Number to Hexadecimal

This problem requires converting a 32-bit integer into its hexadecimal representation without using built-in library functions for hexadecimal conversion. The solution involves manipulating bits and understanding hexadecimal representation.

Core Idea:

Hexadecimal (base-16) uses 16 symbols (0-9 and a-f) to represent numbers. Each hexadecimal digit represents 4 bits (a nibble). The algorithm iterates through the input number's bits in groups of 4 (nibbles), converts each nibble to its hexadecimal equivalent, and concatenates the results to form the final hexadecimal string.

Algorithm:

1. Handle Zero: If the input num is 0, return "0".

2. Iteration: The code iterates through the bits of num from the most significant bit (MSB) to the least significant bit (LSB). Each iteration extracts a nibble using bitwise operations.

3. Nibble Extraction: The expression (num >> (4 * i)) & 0xF extracts the i-th nibble.

   • (num >> (4 * i)): Right-shifts the number by 4 * i bits, bringing the i-th nibble to the least significant position.
   • & 0xF: Performs a bitwise AND with 15 (0xF in hexadecimal), masking out all bits except the least significant 4 bits (the nibble).

4. Hexadecimal Conversion: The extracted nibble (0-15) is converted to its hexadecimal character equivalent:

   • If the nibble is between 0 and 9, it's directly converted to its character representation ('0' to '9').
   • If the nibble is between 10 and 15, it's converted to its lowercase character representation ('a' to 'f').

5. Concatenation: The hexadecimal character is appended to a string or string builder.

6. Return Value: After processing all nibbles, the resulting string (in reverse order in some solutions) is returned.

Time Complexity Analysis:

The algorithm iterates through the bits of a 32-bit integer. This means the loop runs a maximum of 8 times (32 bits / 4 bits per nibble). All other operations within the loop (bitwise operations, character conversions) take constant time. Therefore, the time complexity is O(1), constant time. It's not dependent on the magnitude of the input integer.

Space Complexity Analysis:

The space used depends on the size of the hexadecimal string representation, which is at most 8 characters (for a 32-bit number). Therefore, the space complexity is also O(1), constant space.

Code Examples (Python and Java):

Python:

class Solution:
    def toHex(self, num: int) -> str:
        if num == 0:
            return "0"
        hex_chars = "0123456789abcdef"
        result = ""
        for i in range(8):  # Process 8 nibbles (32 bits)
            nibble = (num >> (4 * i)) & 0xF  # Extract nibble
            result = hex_chars[nibble] + result  # Prepend hex character
        return result.lstrip("0") #Remove leading zeros if any
 

Java:

class Solution {
    public String toHex(int num) {
        if (num == 0) return "0";
        char[] hex = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
        StringBuilder sb = new StringBuilder();
        while (num != 0) {
            sb.append(hex[num & 0xF]); //Append the last nibble's hex representation
            num >>>= 4; //Unsigned right shift by 4 bits
        }
        return sb.reverse().toString(); //Reverse to correct order
    }
}

The provided solutions in other languages (C++, Go) follow a very similar approach, differing only slightly in syntax and standard library usage. The key idea of nibble extraction, hexadecimal conversion, and concatenation remains consistent across all implementations.