LeetCode 504. 七进制数

题目

504. 七进制数

在这里插入图片描述

倒推+迭代

一个整数的七进制可表示为： $num_{7}:\overline{a_{0}a_{1}\dots a_{n-1}}$ ，其中其中 $n$ 为其七进制表示的位数， $a_0$ 为最高位， $a_{n-1}$ 为最低位

其对应的十进制表示为：$num_{10}=\sum_{i=0}^{n-1}a_{i}\times 7^{n-1-i} $。

当要计算一个十进制数对应的七进制表示时，可以先计算最低位 $a_{n-1} = \textit{num}_{10} \bmod 7$ ，因为 $\textit{num}_{10}$ 中对 7 有余的部分仅由 $a_{n-1}$ 贡献。

从两边都减去最低位 $a_{n-1}$ 可得：
$num_{10}-a_{n-1}=\sum_{i=0}^{n-2}a_{i} \times 7^{n - 1 - i}$
两边都除以7，可得：
$\frac{num_{10}-a_{n-1}}{7}=\sum_{i=0}^{n-2}a_{i} \times 7^{n - 2 - i}$
此时， $\frac{num_{10}-a_{n-1}}{7}$ 中对7有余的部分仅由 $a_{n-2}$ 贡献，可得：
$a_{n-2} =\frac{num_{10}-a_{n-1}}{7} \bmod 7$
不停迭代，可以从最低位到最高位还原出 $\textit{num}_7$ 的各位数字，直到 $\textit{num}_{10}$ 归 0。

当输入为负时，可以先取 $\textit{num}$ 的绝对值来求七进制，最后再添加负号。

class Solution {
    public String convertToBase7(int num) {
        if (num == 0) {
            return "0";
        }
        boolean negative = num < 0;
        num = Math.abs(num);
        StringBuffer digits = new StringBuffer();
        while (num > 0) {
            digits.append(num % 7);
            num /= 7;
        }
        if (negative) {
            digits.append('-');
        }
        return digits.reverse().toString();
    }
}

时间复杂度： $O(\log |\textit{num}|)$ ，其中 $|\textit{num}|$ 表示 $\textit{num}$ 的绝对值。循环中最多做 $\log |\textit{num}|$ 次除法。
空间复杂度： $O(\log |\textit{num}|)$ 。字符数组的长度最多为 $\log |\textit{num}|$ 。

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

题目

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

在这里插入图片描述

方法一：位运算 + 分组换算

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

实现一：

class Solution {
    public String toHex(int num) {
        if (num == 0) {
            return "0";
        }
        char[] chars = {'0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f'};
        StringBuilder res = new StringBuilder();
        while (num != 0) {
            // num 的二进制数按照四位一组分组，依次将每一组转换为对应的十六进制数
            res.append(chars[num & 0xf]);
            // 无符号右移
            num >>>= 4;
        }
        return res.reverse().toString();
    }
}

实现二：

class Solution {
    public String toHex(int num) {
        if (num == 0) return "0";
        StringBuilder sb = new StringBuilder();
        while (num != 0) {
            int u = num & 15;
            char c = (char)(u + '0');
            if (u >= 10) c = (char)(u - 10 + 'a');
            sb.append(c);
            num >>>= 4;
        }
        return sb.reverse().toString();
    }
}

Java中：

>>：带符号右移。正数右移高位补0，负数右移高位补1

>>>：无符号右移。无论是正数还是负数，高位通通补0

实现三：

class Solution {
    public String toHex(int num) {
        if (num == 0) {
            return "0";
        }
        StringBuffer sb = new StringBuffer();
        // 从最高4位开始转换
        for (int i = 7; i >= 0; i --) {
            int val = (num >> (4 * i)) & 0xf;
            // 防止前导 0 
            if (sb.length() > 0 || val > 0) {
                char digit = val < 10 ? (char) ('0' + val) : (char) ('a' + val - 10);
                sb.append(digit);
            }
        }
        return sb.toString();
    }
}

方法二：倒推 + 迭代

可以利用通用的进制转换思路来做（例如504. 七进制数），不断循环 num % k 和 num / k 的操作来构造出 k 进制每一位。

但需要处理「补码」问题：对于负数的 $n u m$ ，需要先在 $n u m$ 基础上加上 $2^{32}$ 的偏移量，再进行进制转换。

CSAPP第一章有介绍2’s Comp. -> Unsigned，也就是用Unsigned的大正数表示Signed负数。举个例子，8位int中-1表示为0b11111111(T)，无符号整数0b11111111(U)表示为 $2^8 - 1$ ，二者在计算机中二进制表示相同，差值为 $2^8$ 。因此先在负数的基础上加上 $2^8$ 即可转化为一个大正数，二者的二进制表示相同。在这里32位整形则将原始负数num加上 $2^{32}$ 先转换成大正数，以无符号整形表示。该无符号整形与原始有符号负数的2进制是一样的

class Solution {
    public String toHex(int _num) {
        if (_num == 0) return "0";
        long num = _num;
        StringBuilder sb = new StringBuilder();
        if(num < 0) num = (long)(Math.pow(2, 32) + num);
        while (num != 0) {
            long u = num % 16;
            char c = (char)(u + '0');
            if (u >= 10) c = (char)(u - 10 + 'a');
            sb.append(c);
            num /= 16;
        }
        return sb.reverse().toString();
    }
}