LeetCode 405. 数字转换为十六进制数 题解，了解进制转换的通用思路。

题目

405. 数字转换为十六进制数

https://leetcode.cn/problems/convert-a-number-to-hexadecimal/

给定一个整数，编写一个算法将这个数转换为十六进制数。对于负整数，我们通常使用 补码运算 方法。

注意:

• 十六进制中所有字母(a-f)都必须是小写。
• 十六进制字符串中不能包含多余的前导零。如果要转化的数为0，那么以单个字符'0’来表示；对于其他情况，十六进制字符串中的第一个字符将不会是0字符。 
• 给定的数确保在32位有符号整数范围内。
• 不能使用任何由库提供的将数字直接转换或格式化为十六进制的方法。

模拟

思路

进制转换的过程与 LeetCode 504. 七进制数 一致。

只不过十六进制的转换，由于数字类型的不足，需加入 abcdef 串做base。

关于补码、数字表示的基础补充：

二进制中数字的表示：使用32个二进制位，第一位表示正负（符号位），其余位表示数值

二进制负数取反+1后，恰好为其相反正数的表示

int32 取值范围：[−2^31,2^31−1]

在十六进制中， [0, 2^{31} - 1][0,2^31−1] 范围内的数对应的十六进制存储方式为 00000000-7fffffff， [-2^31,-1][−2^31−1] 范围内的数对应的十六进制存储方式为 80000000-ffffffff。

因此对于入参num，我们判断如果是负数，则将其转换到 long64位的空间中，所有32位int负数，+2^32 后，结果正好处于：[2^31, 2^32-1]。

对于此时的每一个int64正数，我们映射到base16的字符串表示上即可。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

public String toHex(int num) {
    if (num == 0) {
        return "0";
    }

    String base16 = "0123456789abcdef";
    long numLong = num < 0 ? (long) num + (1L << 32) : num;

    StringBuilder builder = new StringBuilder();
    while (numLong > 0) {
        long quotient = numLong / 16;
        long remainder = numLong % 16;
        builder.insert(0, base16.charAt((int) remainder));
        numLong = quotient;
    }
    return builder.toString();
}

复杂度分析

时间

迭代对数次：复杂度O(logn)。

空间

无额外空间占用，空间复杂度O(1)。