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

方法一：位运算

题目要求将给定的整数 num 转换为十六进制数，负整数使用补码运算方法。

在补码运算中，最高位表示符号位，符号位是 0 表示正整数和零，符号位是 1 表示负整数。32 位有符号整数的二进制数有 32 位，由于一位十六进制数对应四位二进制数，因此 32 位有符号整数的十六进制数有 8 位。将 num 的二进制数按照四位一组分成 8 组，依次将每一组转换为对应的十六进制数，即可得到 num 的十六进制数。

假设二进制数的 8 组从低位到高位依次是第 0 组到第 7 组，则对于第 i 组，可以通过 (num >> (4×i)) & 0xf 得到该组的值，其取值范围是 0 到 15（即十六进制的 f）。将每一组的值转换为十六进制数的做法如下：

对于 0 到 9，数字本身就是十六进制数；对于 10 到 15，将其转换为 a 到 f 中的对应字母。

对于负整数，由于最高位一定不是 0，因此不会出现前导零。对于零和正整数，可能出现前导零。避免前导零的做法如下：
如果 num = 0，则直接返回 0；
如果 num > 0，则在遍历每一组的值时，从第一个不是 0 的值开始拼接成十六进制数。

计算机存储 32 位有符号整数。int 型整数存储范围在 [ − 2 31 , 2 31 − 1 ] [-2^{31}, 2^{31} - 1] [−231,231−1] 内，且在计算机内部以补码形式表示，共 32 位，最高位为符号位，负数符号位为 1，正数为 0。

在计算机中， [ 0 , 2 31 − 1 ] [0, 2^{31} - 1] [0,231−1] 范围内的数对应的十六进制存储方式为 0x00000000-0x7FFFFFFF， [ − 2 31 , − 1 ] [-2^{31},-1] [−231,−1] 范围内的数对应的十六进制存储方式为 0x80000000-0xFFFFFFF$。所以，我们可以先将负数统一加上 2 32 2^{32} 232，使其映射到 [ 2 31 , 2 32 − 1 ] [2^{31}, 2^{32} - 1] [231,232−1] 范围内，就可以直接进行十六进制转换了。

为了方便起见，我们提前将十六进制对应的 16 种不同字符存到字符串 s 中，方便进制转换过程中直接提取。

输入为 0 时，直接返回 “0” ;
输入为正数时，通过不断求余数，最后翻转字符串得到十六进制表示；
输入为负数时，利用补码运算的方法，计算其补码运算后的数字，按正数步骤处理，最后处理符号位，注意，输入负数最小值时，补码运算后为 0 ，与输入为 0 要区分，特殊处理。

python 获取负数补码形式

python 数的存储特性，理论上无限！但是负数二进制 bin(-5) 函数返回的是原码前面加个负号 ‘-0b101’ ？同样的 hex 十六进制函数也是这样返回，hex(-5) -> ‘-0x5’。

而 python 中储存无上限，最高位是【符号位】去看待 python 的数字，错误！！“可以说：python 中没有符号位这样的说法”。

a = 0xffffffff  # 32 位 -1 的补码？？？
b = 5
print(hex(b), hex(a), a)  # 0x5 0xffffffff 4294967295

从上看到，python 不认帐的，全是正数，那么这样写与 -1 有什么区别呢？？

print(0xffffffff & -5, -5 & -1)  # 4294967291 -5

python 中负数补码前面有无限个 1 表示负数，比如 5 的补码形式是 ( 0 ) i n f 101 ( 0 ) (0)_{inf}101(0) (0)inf​101(0)，而负数 -5 的补码是 ( 1 ) i n f 011 ( 1 ) (1)_{inf}011(1) (1)inf​011(1) ，也就是前面有无限个 1，直接用 hex 或者 bin 获取负数的补码形式是让人觉得很奇怪的结果。

因而一个常规的操作，根据本题题意来将负数全部转为正数处理，这样就不会出现负数的 hex 函数出现前置 - 了。

那么就本题举例 -1 的 32 位补码形式应该是 0xffffffff，调用 hex 函数之前，先把负数转化为正数看待，即 num & 0xFFFFFFFF，所以 -1 变成正数 0xffffffff，那么 hex 函数就不会出错了，其他负数同理。

也就是使用 & 操作符，把负数前置无限个 1 和 正数 0xFFFFFFFF 前置无限个 0 与运算，那么负数前置的 1 全部被干掉成为 0，即成为正数，是 python 中获取 【x 位整型】负数补码形式的一种操作。

class Solution:
    def toHex(self, num: int) -> str:
        # return f'{num & 0xffffffff:x}'
        return hex(num & 0xFFFFFFFF)[2:]

对于正数而言：
num / 16的商做为下一次的被除数，num / 16的余数被保留（实则为结果16进制的低位）

对于负数而言：
将 num 转换为补码形式，使用 unsigned int 表示，再进行转换，如 -10，使用 8bit 表示为 1111 0110（使用 unsigned int）表示以进行转换
所以当 num < 0时，使用 2^32 + num(num为负数)，得到无符号的数字，再按正数进行转换。

class Solution:
    def toHex(self, num: int) -> str:
        lib, ret = "0123456789abcdef", ""
        # 加上 2**32
        #  1 << 32 = 2 ** 32 = -1 & 0xffffffff + 1 = 4294967296
        # n = num + (1 << 32) if num < 0 else num 
        n = num & 0xffffffff 
        if n == 0: return "0"      

        while n:            
            # ret = lib[n % 16] + ret            
            # n //= 16

            ret = lib[n & 0xf] + ret # 掩码 0X0000000F -> 15
            n >>=  4  
            
        return ret