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

🟢   🔖  位运算 数学  🔗 力扣 LeetCode

题目

Given a 32-bit integer num, return a string representing its hexadecimal representation. For negative integers, two's complement 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:

• -2^31 <= num <= 2^31 - 1

题目大意

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

答案字符串中的所有字母都应该是小写字符，并且除了 0 本身之外，答案中不应该有任何前置零。

注意: 不允许使用任何由库提供的将数字直接转换或格式化为十六进制的方法来解决这个问题。

示例 1：

输入： num = 26

输出： "1a"

示例 2：

输入： num = -1

输出： "ffffffff"

提示：

• -2^31 <= num <= 2^31 - 1

解题思路

1. 处理特殊情况：

   • 如果 num 等于 0，直接返回字符串 '0'。

2. 负数处理：

   • 在 JavaScript 中，负数的二进制表示是 补码，需要将其视为无符号整数。
   • 使用 num >>>= 0 将负数转换为无符号整数，这将有效地处理负数情况。

3. 十六进制字符映射：

   • 十六进制的有效字符为：0, 1, 2, ... 9, a, b, c, d, e, f。
   • 定义一个十六进制字符映射字符串 hexas = '0123456789abcdef'，其中索引位置与十六进制数字一一对应。

4. 转换过程：

   • 使用位运算从整数中提取最低 4 位的二进制位，因为每 4 位可以表示一个十六进制字符。
   • 使用 num & 15 提取最低的 4 位（二进制 1111 等于十六进制 f）。
   • 然后根据 hexas 字符串找到对应的十六进制字符，并将其添加到结果字符串中。
   • 通过 num >>>= 4 将整数向右移动 4 位，丢弃已经处理过的最低 4 位。
   • 重复此过程，直到 num 为 0。

5. 返回结果：

   • 最终结果是从最低位开始构建的，所以需要拼接字符时将新的字符放在结果字符串的前面。

复杂度分析

• 时间复杂度：O(1)，每次循环将 num 右移 4 位，最多需要处理 32 / 4 = 8次（32 位整数），因此复杂度为 O(8) = O(1)。
• 空间复杂度：O(1)，除了常数空间 hexas 和结果字符串外，没有额外使用空间。

代码

/**
 * @param {number} num
 * @return {string}
 */
var toHex = function (num) {
	const hexas = '0123456789abcdef'; // 十六进制字符映射
	if (num === 0) return '0'; // 特殊情况：num 为 0

	if (num < 0) {
		// 负数处理，将负数转换为无符号整数形式
		num >>>= 0;
	}

	let res = '';
	while (num > 0) {
		// 提取最低 4 位的值，并找到对应的十六进制字符
		res = hexas[num & 15] + res;
		// 将 num 右移 4 位，继续处理下一组 4 位
		num >>>= 4;
	}

	return res;
};