405. 数字转换为十六进制数 ——【Leetcode每日一题】

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

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

注意:

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

不能使用任何由库提供的将数字直接转换或格式化为十六进制的方法。

示例 1：

输入:
26
输出:
“1a”

示例 2：

输入:
-1
输出:
“ffffffff”

思路：

法一：进制转换

我们可以利用通用的进制转换思路来做:

• 正数的补码还是它本身，只需要不断循环 num % k 和 num / k 的操作来构造出 k 进制每一位。
• 但负数需要处理补码问题：对于负数的，我们需要先在 num 基础上加上 $2^{32}$ 的偏移量，再进行进制转换。

法二：位运算

计算机中每4位二进制，对应1位十六进制：

• 使用 0xf (00…01111b)获取 num 的低4位。
• >> 算数位移，其中正数右移左边补0，负数右移左边补1。
• 位移运算并不能保证num==0，需要使用32位int保证（对应16进制小于等于8位）。

代码：(Java、C++)

法一：进制转换：
(C++)

#include<iostream>
using namespace std;
#include<string>

string toHex(int num) {
	if (num == 0) {
			return "0";
	}
	long long n = num;//C++中的int 和 long 都是占4个字节，32位，需要用占8字节的long long
	string ans;
	if (n < 0) {
		n += pow(2, 32);
	}
	while (n != 0) {
		long tem = n % 16;
		ans = (char)(tem > 9 ? (tem - 10 + 'a') : (tem + '0')) + ans;
		n /= 16;
	}
	return ans;
}
int main() {

	int num = -1;
	cout <<toHex(num) << endl;
	return 0;
}

法二：位运算
(java)

public class ToHex {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int num = -1;
		System.out.println(toHex(num));
	}
	public static 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'};
        if (num == 0) return "0";
        StringBuilder sb = new StringBuilder();
        while (num != 0) {
            sb.append(map[num & 0xf]);
            num >>>= 4; // 因为考虑的是补码形式，因此符号位就不能有特殊的意义，需要使用无符号右移，左边填 0
        }
        return sb.reverse().toString();
    }
}

(C++)

#include<iostream>
using namespace std;
#include<string>

string toHex(int num) {
	if (num == 0) {
		return "0";
	}
	string ans = "";
	char map[] = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };

	while (num != 0 && ans.size() < 8) {
		ans = map[num & 0xf] + ans;
		num >>= 4;
	}
	return ans;
}
int main() {

	int num = -1;
	cout <<toHex(num) << endl;
	return 0;
}

运行结果：

力扣提交：

复杂度分析：

• 时间复杂度：复杂度取决于构造的十六进制数的长度，固定为 $C=8$。整体复杂度为 $O(C)$。
• 空间复杂度：复杂度取决于构造的十六进制数的长度，固定为 $C=8$。整体复杂度为 $O(C)$。

注：仅供学习参考， 如有不足，欢迎指正！

题目来源：力扣。