LeetCode 405. Convert a Number t

题目

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"
**Example 2:**
Input:-1
Output:"ffffffff"

解析

首先要说明一下计算机是如何存储整数的。
对于单字节（8位）的整数，如果为unsigned，其取值范围为0-255；如果为signed，范围为-128-127。因为有符号的会把最高位拿出来用作符号标识，因为取值就折半了。
在计算机中，数值一律使用补码的形式来存储。正数的补码为其本身，而负数的补码为其反码+1。因此可知，-1的补码为ff。
此题是求解hex，首先需要得到hex的宽度，然后再使用移位运算依次去拿低四位的值，并转换为hex存储。依次循环就得到整个hex string。

代码

int getHexSize(int num);
char* toHex(int num) {
    uint32_t uNum = num;
    int hexSize = getHexSize(uNum);
    
    char* hexStr = (char*)calloc(hexSize + 1, sizeof(char));
    hexStr[hexSize] = '\0';
    
    if (uNum == 0) {
        hexStr[0] = '0';
        return hexStr;
    }
    
    int index = hexSize - 1;
    char* hexCharMap = "0123456789abcdef";
    
    while (uNum > 0) {
        hexStr[index] = hexCharMap[uNum & 15];
        
        uNum >>= 4;
        --index;
    }
    
    return hexStr;
}

int getHexSize(int num) {
    int mask = 16, size = 1;
    
    while ((num & (mask - 1)) != num) {
        mask <<= 4;
        ++size;
    }
    
    return size;
}

getHexSize是获取结果的hex宽度，其主要是使用4位的移位和&运算共同获得。num & 1111...，如果111宽度大于num的二进制宽度，则其结果为num本身，这时的size为hex宽度。
程序中使用uint32_t存储负数的补码值，也是uint32_t的原码值，这样处理起来不用考虑符号位，比较方便。