支持负数的16进制转换

原题

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

注意:

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

原题链接

思路

非负整数的进制转换是一道简单的循环题，取模再自除就可以完成了。

1
2
3
4
5
6
7
8
9
10
11
12
13

string toHex(int num) {
	if (!num) return "0";
	string res;
	char c;
	while (num) {
		int temp = num % 16;
		if (temp >= 10) c = char(temp - 10 + 'A');
		else c = char(temp + '0');
		res = c + res;
		num /= 16;
	}
	return res;
}

位操作

但这个代码并不支持负数的转换。

注意到题目说明

对于负整数，我们通常使用 补码运算 方法。

补码运算的相关知识见之前的文章。二进制下的负数

既然计算机中都是用二进制存储的，负数的二进制已经是补码形式了，我们就不需要考虑负数怎么转换了，跟正数二进制转十六进制一样。

那我们可以直接操纵二进制来实现进制转换。

二进制与十六进制

注意到二进制每四个数位对应十六进制的一个数位。

1
2

BIN(1011 1100 0100)
HEX(BC4)

来看二进制最前面的四位，1011的十进制表示为11，这不就跟十六进制最前面的B对上了嘛。

同理，1100十进制是12，也就是十六进制的C。

0100十进制为4，十六进制也是4。

如此方便转换，这也是为什么计算机中许多数据可以用16进制来显示（例如内存地址）。

ok,现在我们有大概的思路了。

通过位操作每次提取二进制中的四位，然后看它们对应十六进制是什么，加上就行了。

如何提取末四位呢？可以用位与操作&，将要提取的数& 0xf。（0xf也就是0b1111）

核心伪代码:

for (i=7->0)
val = (num >> (i * 4)) & 0xf;

第一句的i从7到0，是因为题目条件保证数据范围在32位整数里，也就是有8组4位二进制。

第二句每次将num移动4的倍数位，最开始移动28位，得到的就是num最高的四位。

依次移动来获得从最高四位到末尾四位。

数据并不能占满前面几位怎么办，题目要求没有前导零。

所以要加个判断，当遇到非零数后才开始往字符串加内容。

代码

1
2
3
4
5
6
7
8
9
10
11
12

string toHex(int num) {
	if (!num) return "0";
	string res = "";
	int val;
	for (int i = 7; i >= 0; --i) {
		val = (num >> (i * 4)) & 0xf;
		if (!val && !res.size()) continue;
		if (val >= 10) res.push_back(char(val - 10 + 'a'));
		else res.push_back(char(val + '0'));
	}
	return res;
}