进制转换

昨天做leetcode的每日一题，进制转换的时候突然联想到了辗转相除法，再跟室友交流之后才弄明白辗转相除法是求最大公约数的，为了捋清楚进制转换问题，在这篇博客里用两种方法解决。

背景：405. 数字转换为十六进制数

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

连除取余法

这个方法比较常规 一直取余数 最后将余数倒着输出就好啦

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    
    def toHex(self, num: int) -> str:
        CONV = "0123456789abcdef"
        ans =[]
        # 32位二进制数 转成十六进制 共8位 4*8
        for _ in range(8): 
            temp = num % 16
            num = num//16
            ans.append(temp)
            if not num:
                break
        # 倒着输出
        return ''.join(CONV[j] for j in ans[::-1])

位运算

这个操作相当秀了。从ACM大佬那里学到一招：将/2操作变成右移一位，与1做与运算判断奇偶性是一个好习惯。

预备知识：

  • 在编程语言中，十进制数做位运算的时候直接是当作二进制数操作的。
  • 右移一位相当于是除2^1 ，显然，转16进制时每次要除16，即2^4 ，右移4位 每除一次得到最高位的十六进制数。

image-20211003085946977

解释两点自己的疑惑：

  • int val = (num >> (4 * i)) & 0xf;

    将二进制数四个一组 转换成十六进制 每次将待转换的四位右移到最低位。与0xf做与运算的原因在于，只取最低4位，其他位全置为0.

  • int i = 7; i >= 0; i —

    从最高位开始 依次加入字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    string toHex(int num) {
        if (num == 0) {
            return "0";
        }
        string sb;
        for (int i = 7; i >= 0; i --) {
            int val = (num >> (4 * i)) & 0xf;
            if (sb.length() > 0 || val > 0) {
                char digit = val < 10 ? (char) ('0' + val) : (char) ('a' + val - 10);
                sb.push_back(digit);
            }
        }
        return sb;
    }
};