# Convert a Number to Hexadecimal
**Difficulty:** EASY
[External](https://leetcode.com/problems/convert-a-number-to-hexadecimal)
Canonical: https://scaleengineer.com/dsa/problems/convert-a-number-to-hexadecimal
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
---
## Problem
Given a 32-bit integer `num`, return _a string representing its hexadecimal representation_. For negative integers, [two’s complement](https://en.wikipedia.org/wiki/Two%27s%5Fcomplement) method is used.

All the letters in the answer string should be lowercase characters, and there should not be any leading zeros in the answer except for the zero itself.

**Note:** You are not allowed to use any built-in library method to directly solve this problem.

**Example 1:**

**Input:** num = 26
**Output:** "1a"

**Example 2:**

**Input:** num = -1
**Output:** "ffffffff"

**Constraints:**

* `-231 <= num <= 231 - 1`

# Approaches
## Mathematical Conversion using Division and Modulo
This approach simulates the standard base conversion algorithm. For positive numbers, we repeatedly divide the number by 16 and use the remainders to form the hexadecimal string. The main challenge is handling negative numbers. In Java, negative numbers are stored in two's complement form. A direct application of division and modulo on a negative `int` will not yield the correct hexadecimal digits. To overcome this, we first convert the 32-bit integer to a 64-bit `long`, preserving its bit pattern. This effectively treats the number as an unsigned 32-bit integer, allowing the standard division/modulo algorithm to work correctly for all inputs.
**Time:** O(1). The input is a 32-bit integer. The `while` loop will run at most `log16(2^32) = 8` times. The operations inside the loop are constant time. Thus, the complexity is constant. · **Space:** O(1). The `StringBuilder` will store at most 8 characters for a 32-bit integer. The space used is constant.
**Pros:** Conceptually simple, as it follows the standard base conversion method taught in mathematics.; Relatively easy to understand for those familiar with base conversion algorithms.
**Cons:** Less efficient than the bitwise approach because division and modulo operations are computationally more expensive than bitwise shifts and ANDs.; Requires using a `long` to correctly handle the unsigned representation of negative 32-bit integers, which uses more memory and adds a conversion step.
### Explanation
The algorithm proceeds as follows:

*   **Handle Zero:** If the input `num` is 0, return "0" immediately, as this is a special case.
*   **Map Characters:** Create a character array `map` that maps integer values from 0 to 15 to their corresponding hexadecimal characters ('0' through '9', then 'a' through 'f').
*   **Unsigned Conversion:** Convert the input `int num` to a `long` to correctly handle the full 32-bit unsigned range. This is achieved by a bitwise AND with the mask `0xFFFFFFFFL`. This step is crucial because it ensures that negative numbers (which have their most significant bit as 1) are treated as large positive values, corresponding to their two's complement representation.
*   **Iterative Conversion:** Initialize an empty `StringBuilder` to construct the result. Loop as long as the `long` value is greater than 0:
    *   Calculate the remainder when the value is divided by 16 (`val % 16`). This remainder will be a number from 0 to 15.
    *   Use this remainder as an index into the `map` to find the correct hex character.
    *   Prepend this character to the `StringBuilder`. Prepending builds the string in the correct order (from least significant to most significant digit).
    *   Update the value by performing an integer division by 16 (`val / 16`).
*   **Return Result:** Once the loop finishes, the `StringBuilder` contains the complete hexadecimal string. Convert it to a `String` and return it.

```java
class Solution {
    public String toHex(int num) {
        if (num == 0) {
            return "0";
        }
        char[] map = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
        StringBuilder sb = new StringBuilder();
        long longNum = num & 0xFFFFFFFFL; // Treat as unsigned 32-bit integer
        
        while (longNum > 0) {
            int remainder = (int) (longNum % 16);
            sb.insert(0, map[remainder]);
            longNum /= 16;
        }
        
        return sb.toString();
    }
}
```
### Algorithm
*   Handle the edge case: if `num == 0`, return "0".
*   Convert the input `int num` to a `long` to handle the full 32-bit unsigned range. This can be done using a bitwise AND with `0xFFFFFFFFL`: `long val = num & 0xFFFFFFFFL;`.
*   Create a character array `map` to map digits 0-15 to their hexadecimal characters '0'-'f'.
*   Initialize an empty `StringBuilder`.
*   Loop while `val` is greater than 0:
    *   Calculate the remainder when `val` is divided by 16: `remainder = val % 16`.
    *   Use the `remainder` as an index into the `map` to get the corresponding hex character.
    *   Prepend this character to the `StringBuilder`.
    *   Update `val` by dividing it by 16: `val = val / 16`.
*   Return the final string from the `StringBuilder`.

## Bitwise Manipulation
This is a highly efficient approach that leverages bitwise operations to extract hexadecimal digits directly from the integer's binary representation. A hexadecimal digit corresponds to 4 bits (a nibble). We can process the number 4 bits at a time, from the least significant bits to the most significant. For each 4-bit chunk, we determine its value (0-15) and map it to the corresponding hex character.
**Time:** O(1). The loop runs a fixed number of times, at most 8 for a 32-bit integer. Bitwise operations (AND, shift) are extremely fast. Therefore, the overall time complexity is constant. · **Space:** O(1). The `StringBuilder` stores a result of at most 8 characters. The space required is constant.
**Pros:** Highly efficient due to the use of fast bitwise operations instead of slower arithmetic division/modulo.; Handles negative numbers elegantly using the unsigned right shift (`>>>`), avoiding the need for type casting to `long` or special conditional logic.; This is the standard and most performant way to perform such conversions at a low level.
**Cons:** May be slightly less intuitive for developers not comfortable with bitwise operations.
### Explanation
This approach directly manipulates the bits of the integer to find its hexadecimal representation. The key insight is that each hexadecimal digit corresponds to exactly 4 bits (a nibble).

*   **Handle Zero:** If the input `num` is 0, return "0".
*   **Map Characters:** Create a character array `map` for '0'-'f' to translate nibble values to characters.
*   **Iterate and Extract Nibbles:** Initialize a `StringBuilder`. The conversion is done in a loop that continues as long as `num` is not zero. This condition works for both positive and negative numbers.
    *   **Isolate Nibble:** In each iteration, isolate the rightmost 4 bits (the least significant nibble) of `num`. This is done using a bitwise AND operation with a mask of `0xF` (binary `00...001111`). The result, `num & 0xF`, is an integer between 0 and 15.
    *   **Map to Character:** Use the result from the previous step as an index into the `map` to get the corresponding hex character.
    *   **Build String:** Prepend the character to the `StringBuilder`.
    *   **Shift for Next Nibble:** Prepare for the next iteration by shifting the bits of `num` 4 places to the right. It is critical to use the **unsigned right shift operator (`>>>`)**. This operator fills the leftmost bits with zeros, effectively treating the number as an unsigned integer. This is how two's complement negative numbers are handled correctly. An arithmetic right shift (`>>`) would fill with the sign bit, leading to an infinite loop for negative numbers.
*   **Return Result:** After the loop terminates (when all bits have been shifted out and `num` becomes 0), return the string from the `StringBuilder`.

```java
class Solution {
    public String toHex(int num) {
        if (num == 0) {
            return "0";
        }
        char[] map = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
        StringBuilder sb = new StringBuilder();
        
        // The loop condition `num != 0` handles both positive and negative numbers.
        // For negative numbers, the unsigned right shift `>>>` will eventually make `num` zero.
        while (num != 0) {
            int digit = num & 0xF; // Get last 4 bits
            sb.insert(0, map[digit]);
            num >>>= 4; // Unsigned right shift
        }
        
        return sb.toString();
    }
}
```
### Algorithm
*   Handle the edge case: if `num == 0`, return "0".
*   Create a character array `map` for '0'-'f'.
*   Initialize an empty `StringBuilder`.
*   Loop as long as `num` is not 0:
    *   Isolate the last 4 bits using a bitwise AND with a mask of `0xF`: `digit = num & 0xF`.
    *   Find the corresponding hex character from the `map` using `digit` as the index.
    *   Prepend this character to the `StringBuilder`.
    *   Shift the bits of `num` 4 places to the right using the unsigned right shift operator `>>>`.
*   Return the string from the `StringBuilder`.

# Solutions
### Java

```java
class Solution { public String toHex ( int num ) { if ( num == 0 ) { return "0" ; } StringBuilder sb = new StringBuilder (); while ( num != 0 ) { int x = num & 15 ; if ( x < 10 ) { sb . append ( x ); } else { sb . append (( char ) ( x - 10 + 'a' )); } num >>>= 4 ; } return sb . reverse (). toString (); } }
```

### CPP

```cpp
class Solution { public: string toHex ( int num ) { if ( num == 0 ) return "0" ; string s = "" ; for ( int i = 7 ; i >= 0 ; -- i ) { int x = ( num >> ( 4 * i )) & 0xf ; if ( s . size () > 0 || x != 0 ) { char c = x < 10 ? ( char ) ( x + '0' ) : ( char ) ( x - 10 + 'a' ); s += c ; } } return s ; } };
```

### Python

```python
class Solution : def toHex ( self , num : int ) -> str : if num == 0 : return '0' chars = '0123456789abcdef' s = [] for i in range ( 7 , - 1 , - 1 ): x = ( num >> ( 4 * i )) & 0xF if s or x != 0 : s . append ( chars [ x ]) return '' . join ( s )
```