405. Convert a Number to Hexadecimal

描述

Given an integer, write an algorithm to convert it to hexadecimal. For negative integer, two’s complement method is used.

Note:

1.All letters in hexadecimal (a-f) must be in lowercase.

2.The hexadecimal string must not contain extra leading 0s. If the number is zero, it is represented by a single zero character ‘0’; otherwise, the first character in the hexadecimal string will not be the zero character.

3.The given number is guaranteed to fit within the range of a 32-bit signed integer.

4.You must not use any method provided by the library which converts/formats the number to hex directly.

Example 1:

Input:
26

Output:
"1a"

Input:
-1

Output:
"ffffffff"

分析

这道题要求我们将一个十进制数转换为十六进制数。

那么对于正数，我们用辗转相除法就很容易求得其十六进制表示，但这道题还要求我们考虑输入为负的情况，我们知道，负数是无法用这个方法进行转换的。

要解决这个问题，我们得先考虑一个十进制数在计算机中是如何存储的。

以3为例,其二进制表示为（考虑int类型为32位）

0000 0000 0000 0000 0000 0000 0000 0011 

我们将这样的某个整数的绝对值的二进制表示称为源码。

那么如果我们对这个二进制串按位取反，可得其反码

1111 1111 1111 1111 1111 1111 1111 1100

反码再+1可得其补码

1111 1111 1111 1111 1111 1111 1111 1101

而补码正是一个负数在计算机中的存储方式，而-3的十六进制表示是

0xfffffffd

所以我们看到，要将一个十进制数转换为十六进制数，不管其是正数还是负数，都只需要将其二进制表示每四位分成一个单元，将其取出后计算这四位二进制数代表的十进制数，与0~f之间的数字做一个映射即可。要把每四位取出也很简单，与0xf进行AND运算即可。代码如下：

class Solution {
public:
    string toHex(int num) {
        string res;
        int low=0,high=0;
        char map[16]={'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'};
        while(num&&res.size()<8){
            res=map[(num&0xf)]+res;
            num=num>>4;
        }
        return res;
    }
};

需要注意的一点是，如果输入为负数，那么我们需要在循环条件中，保证要返回的字符串长度小于8，因为输入是32位int类型。这和负数计算机中的存储方式和C++中的右移运算符有关。

在C++中，左移是逻辑移位，也就是说在数字后面补0，右移运算符是算术移位，也就是在左侧补符号位(正数补0，负数补1，不同编译环境可能不一样)，所以我们以-128为例，每次右移1位，右移10次来查看结果，如下:

-64
-32
-16
-8
-4
-2
-1
-1
-1
-1

因为不断在左边补1，而-1在计算机中以1111 1111存储(补码)，所以无论再怎么右移，最后得到的二进制串在经过-1，取反后得到的真值永远是-1，那么循环条件如果只有num!=0，就会陷入死循环。

这道题不仅考查了正数的十进制与十六进制的转换，还通过将负数引入测试样例的方法让我们思考一个数在计算机中究竟是怎么存储的以及C++中右移运算符的特殊性，是一道非常综合的题目，值得反复琢磨。