再谈进制转换

发表于 | 更新于 | 阅读次数：

之前已经详细的讨论了十进制整数以及小数和二进制之间的互转，详细的可以参考 理解进制转换的原理。

前段时间在 知乎 看到了这样的一个问题。

你品，你细品，如果让你把 7 进制数转成 8 进制数，是不是你会先把 7 进制数转成 10 进制数，然后再转成 8 进制数。下边就讨论一下这个问题，前提是你已经对二进制和十进制之间的互转已经很清楚了。不然的话，建议先看一下 理解进制转换的原理。

我们再重新思考一下进制，所谓进制无非是每一位有了不同的权重。

对于二进制权重依次是 $$…2^32^22^12^0$$

也就是 ... 8 4 2 1

所以对于二进制 1100 ，转为十进制就是二进制的每一位乘以它的权重，即

1 × 8 + 1 × 4 + 0 × 2 + 0 × 1 = 12。

那么问题来了，为什么是转成了十进制？

这里是关键了，因为我们说权重的时候，习惯性就用 10 进制去计算了权重。

那么这里换下思路，我们不用十进制去表示权重，而是用七进制去表示权重。

让我们熟悉一下七进制。

首先七进制用 7 个符号表示，即 0, 1, 2, 3, 4, 5, 6

再熟悉一下七进制的运算，满 7 进 1

2 + 6 = 11

3 + 4 = 10

2 * 2 = 4

$2^3=11$

好的，看起来有些别扭，但事实如此，哈哈。

让我们回到二进制的权重问题，看一下七进制下的权重。

对于二进制权重依次是 $$…2^32^22^12^0$$

也就是，... 11 4 2 1

所以对于二进制 1100 ，转为七进制就是二进制的每一位乘以它的权重，即

1 × 11 + 1 × 4 + 0 × 2 + 0 × 1 = 11 + 4 = 15

所以二进制的 1100 在七进制中就是 15。

我们直接将二进制转为了七进制！

所以，我们之所以要将其他进制先转换为十进制，就是因为进制的权重我们默认下都是在十进制下进行的。如果在程序中，我们算某个权重，比如 $2^3$，结果一定是 8，这也决定了，我们只能将其它进制先转为十进制。

1
2
3
4
5
6
7
8
9
10
11
public int twoToTen(String two) {
	char[] array = two.toCharArray();
	int n = array.length;
	int sum = 0;
	int power = 0;
	for (int i = n - 1; i >= 0; i--) {
		sum = sum + (array[i] - '0') * (int) Math.pow(2, power);
		power++;
	}
	return sum;
}

输入二进制 1100，就会输出十进制的 12 了。

为什么是 10 进制的呢，因为上边我们累加以及算权重的时候，调用的加法、乘法、幂次，都是基于 10 进制的。

那么我们能否修改函数，直接把二进制转为七进制呢？

我们只需要重新定义加法、乘法、以及幂次，让运算都是基于七进制的即可。这样算出的权重就是基于七进制的，加法、乘法也就会是基于七进制的，最终的结果当然是一个七进制的数字了。

首先我们定义一个 Seven 类，进行七进制的加法以及乘法、幂次。

思想的话，参考 Leetcode 的第二题 大数相加 。

这里的乘法以及幂次，直接递归的进行了，没有进行任何优化，只用于演示，具体优化方法参考可以参考 LeetCode 的 29 题 以及 50 题。

此外，这里的加法只考虑了两个正数相加，减法也只考虑了减 1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public final class Seven {
    public static int sum(int n1, int n2) {
        int res = 0;
        int carry = 0;
        int shift = 1;
        while (n1 != 0 || n2 != 0) {
            int x = (n1 != 0) ? n1 % 10 : 0;
            int y = (n2 != 0) ? n2 % 10 : 0;
            int sum = carry + x + y;
            carry = sum / 7; //保存进位
            res = res + sum % 7 * shift;
            n1 /= 10;
            n2 /= 10;
            shift *= 10;
        }
        if (carry != 0) {
            res = res + 1 * shift;
        }
        return res;
    }

    //传进来的数是七进制, 实现减 1
    public static int subOne(int n) {
        int count = 0;
        //考虑需要借位的情况，比如这种 43000
        while (n % 10 == 0) {
            n /= 10;
            count++;
        }
        n -= 1; //借位
        //低位补 6
        while (count != 0) {
            n = n * 10 + 6;
            count--;
        }
        return n;

    }

    public static int mul(int n1, int n2) {
        if (n2 == 0) {
            return 0;
        }
        return Seven.sum(n1, mul(n1, Seven.subOne(n2)));
    }

    public static int pow(int a, int b) {
        if (b == 0) {
            return 1;
        }
        return Seven.mul(a, pow(a, Seven.subOne(b)));
    }
}

有了七进制运算的类，我们就可以直接把二进制直接转换为七进制了。

1
2
3
4
5
6
7
8
9
10
11
12
13
public int twoToSeven(String two) {
	char[] array = two.toCharArray();
	int n = array.length;
	int sum = 0;
	int power = 0;
	for (int i = n - 1; i >= 0; i--) {
		int pow = Seven.pow(2, power);
		int mul = Seven.mul(array[i] - '0', pow);
		sum = Seven.sum(sum, mul);
		power++;
	}
	return sum;
}

上边如果输入 1100，就会输出七进制的 15 了。

甚至，我们可以在函数增加一个参数，就可以将任意进制转为七进制了。

1
2
3
4
5
6
7
8
9
10
11
12
13
public int anyToSeven(String two, int radix) {
	char[] array = two.toCharArray();
	int n = array.length;
	int sum = 0;
	int power = 0;
	for (int i = n - 1; i >= 0; i--) {
		int pow = Seven.pow(radix, power);
		int mul = Seven.mul(array[i] - '0', pow);
		sum = Seven.sum(sum, mul);
		power++;
	}
	return sum;
}

上边如果输入 1200 3，也就是三进制的 1200，就会输出七进制的 63 了。

当然上边的 any 只能是小于七进制的，因为我们里边的运算都是基于 7 进制的，允许的符号是 0 - 6，如果大于七进制上边就会乱套了。

至于大于七进制的转为七进制，方法的话就类似于上边介绍的十进制转为二进制，此时权重是固定的，然后利用除法求出每一位的值。

因此我们至少还需要实现七进制的除法，然后利用十进制转为二进制的思想即可。这里就不写了，就交给大家了，哈哈。

ps: 上边的代码，没有做严格的测试，思想应该是对的，哈哈，发现问题可以和我交流。

总结一下

进制转换分为两大类。

低进制转到高进制，也就是我们上边详细讨论的。我们只需要把权重用高进制的数去表示，然后在某个进制下进行相乘相加即可。

高进制转到低进制，类比于我们熟悉的十进制转二进制，同样用高进制的数表示权重，此时我们在某个进制下通过除法来求出各个位即可。

其实不管高进制到低进制，还是低进制到高进制，都是基于下边的等式。

以十进制和二进制的转换为例。

$$…a\times2^4+b\times2^3+c\times2^2+d\times2^1+e\times2^0=2020$$

已知左边，就是低进制到高进制。已知右边，就是高进制到低进制。

左边权重的幂次的底决定了低进制是多少。

相乘相加在多少进制下进行，决定了最终转为了多少进制。

因此需要十进制中转根本原因就是我们手里的计算器，计算机，或者你自己的口算，所有的计算我们都默认在十进制下进行，数量这个概念我们也是用十进制表示的。

因此不管其他进制转十进制，还是十进制转其他进制都会很方便。

再补一句，如果自己去实现七进制下的加减乘除。为了减少我们的工作量，因为我们的计算机已经实现了十进制的加减乘除，所以我们可以将七进制转为十进制，然后进行相应的计算，最后再将结果转回七进制即可。而我之前实现的七进制类，相当于在十进制的基础上模拟了七进制的进位借位，所以更麻烦些。

windliang wechat