再谈进制转换

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

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

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

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

对于二进制权重依次是

也就是 ... 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

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

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

对于二进制权重依次是

也就是，... 11 4 2 1

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

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

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

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

所以，我们之所以要将其他进制先转换为十进制，就是因为进制的权重我们默认下都是在十进制下进行的。如果在程序中，我们算某个权重，比如

，结果一定是 8，这也决定了，我们只能将其它进制先转为十进制。

代码语言：javascript复制

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。

代码语言：javascript复制

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)));
    }
}

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

代码语言：javascript复制

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 了。

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

代码语言：javascript复制

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: 上边的代码，没有做严格的测试，思想应该是对的，哈哈，发现问题可以和我交流。