算法数学算法

进制转换

字数统计: 2k字   |   阅读时长: 8分
, , ,

摘要: 进制转换的算法、代码模板、例题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在进制转换当中，我们比较熟悉的是二进制和十进制之间的互相转换。有时候我们会遇到 k 进制与 10 进制互相转换的问题，这里 $k > 0$，本文我们就来看一下 k 进制数与 10 进制互相转换的问题。首先讨论下面这四种情况的算法：

  • 十进制整数转 k 进制
  • 十进制小数部分转 k 进制
  • k 进制整数转十进制
  • k 进制小数部分转十进制

对于一个带小数十进制数与k进制互相转换，均可以把整数部分和小数部分分开进行转换，然后在连接在一起。

其中十进制转 k 进制的算法是短除法；k 进制转十进制的算法是按权相加法。后续均给出了代码模板。

然后我们解决力扣上几个进制转换的问题：力扣 504、483、405。

$1 十进制转k进制(k>0)

进制转换的算法为短除法，这个算法就可以直接处理负整数的转换。

如果是转换为二进制并取补码，则在结果上取反加一即可。

(1) 十进制整数部分转k进制(k>0)

算法：短除法

以十进制转七进制(k=7)为例。

十进制数 x=4312，对应的七进制数为 15400。

短除法过程如图：不断迭代 x 除以 7 的商，直到商小于 7，右边为每次迭代的余数。迭代完成后将右边一列数倒着写就是转换进制后的数字。

短除法

模板题

给定一个整数 num，将其转化为 7 进制，并以字符串形式输出。

提示：

1
-1e7 <= num <= 1e7

示例 1:
输入: num = 100
输出: “202”

示例 2:
输入: num = -7
输出: “-10”

代码 (C++) (模板)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    string convertToBase7(int num) {
        if(num == 0) return "0";
        bool nega = false;
        if(num < 0)
        {
            nega = true;
            num = -num;
        }
        string result = "";
        int base = 7;
        while(num > 0)
        {
            int r = num % base;
            num /= base;
            result += '0' + r;
        }
        if(nega) result += '-';
        reverse(result.begin(), result.end());
        return result;
    }
};

(2) 十进制小数部分转k进制

以十进制转二进制为例：

x=0.25 转换成 2 进制的结果为 0.01，转换过程如下：

1
2
3
首先将 x=0.25 乘以 2 得数为 0.5，取其整数部分 0，取 x 为小数部分
接着把 x=0.5 再乘以 2 得数为 1.0，取其整数部分 1，取 x 为小数部分
直至x为0为止，最后结果按照正序排列即可。得数为0.01

$2 k进制转十进制

(1) k进制整数部分转十进制(按权相加法)

以二进制为例：

二进制数 1000001 的十进制数为 65，转换过程如下：

1
2
// 低位 -> 高位
1*2^0 + 0*2^1 + 0*2^2 + 0*2^3 + 0*2^4 + 0*2^5 + 1*2^6 = 65

代码模板 (C++)

1
2
3
4
5
6
7
8
9
10
11
ll convertToBase10(const string& num, ll base) {
    if(num == "0") return 0;
    ll result = 0;
    ll p = 1;
    for(int i = num.size() - 1; i >= 0; --i)
    {
        result += (num[i] - '0') * p;
        p *= base;
    }
    return result;
}

(2) k进制小数部分转十进制(按权相加法)

以二进制数为例：

二进制代码为 0.01 的十进制数为 0.25，转换过程：

1
0*2^(-1) + 1*2^(-2) = 0.25

从小数点后面的第一位对应 2 的负 1 次方，第二位对应 2 的负2次方，以此类推。

$3 题目

483. 最小好进制

以字符串的形式给出 n , 以字符串的形式返回 n 的最小 好进制 。

如果 n 的 k(k>=2) 进制数的所有数位全为1，则称 k(k>=2) 是 n 的一个 好进制 。

提示：

1
2
n 的取值范围是 [3, 1e18]
n 没有前导 0

示例 1：
输入：n = “13”
输出：”3”
解释：13 的 3 进制是 111。

示例 2：
输入：n = “4681”
输出：”8”
解释：4681 的 8 进制是 11111。

示例 3：
输入：n = “1000000000000000000”
输出：”999999999999999999”
解释：1000000000000000000 的 999999999999999999 进制是 11。

算法：二分 + 进制转换(k 转 10)

n 的范围为 [3, 1e18]

1e18 对应的二进制是 57 位。即 n 取到最大，k 取到最小，所得 k 进制序列也就是 57 位。

k 越小，相当于所得 k 进制序列越大。因此倒序可以枚举最终序列的长度 len，问：是否有某个进制 k，使得最终序列为 len 个 1，若存在，则返回找到的 k，若不存在，则 len 自减后继续询问，直至 len = 1;

问题转化成了：给定十进制数 n，和 len，问是否有某个 k，转成 k 进制后为 len 个 1，记为 target。

二分 k，通过进制转换算法求出 n 的 k 进制序列 y

  • y == target: 找到答案 k
  • y > target: 进制数 k 选小了，left = mid + 1
  • y < target: 进制数 k 选大了，right = mid - 1

但是由于 k 的范围很大，y 的表示很难实现，因此逆向思维，将 k 进制的 target 转换为 10 进制得到 z，然后与 n 比较。

  • z == n: 找到答案 k
  • z > n: 进制数 k 选大了，right = mid - 1
  • z < n: 进制数 k 选小了，left = mid + 1
1
2
3
4
5
6
7
8
求 n 的二进制序列 y，其长度 L，若 y 全 1，则返回 2，否则迭代最终序列长度 len: [L-1..2]:
    target = string(len, '1');
    二分 k: [l, r] = [3, n-1]
        mid = (l + r) / 2
        ll z = convertToBase10(n, mid)
        1) z == n`: 找到答案 mid
        2) z > n`: 进制数 k 选大了，right = mid - 1
        3) z < n`: 进制数 k 选小了，left = mid + 1

代码 (C++)

进制转换和比大小放在一起实现，进制转换的迭代过程中出现 result 大于 N 了，可以早停。

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
using ll = long long;

class Solution {
public:
    string smallestGoodBase(string n) {
        // 1e18 >= n >= 3
        ll N;
        stringstream ss;
        ss << n;
        ss >> N;
        int L = log2(N) + 1;
        while(L > 1)
        {
            ll l = 2, r = N - 1;
            while(l <= r)
            {
                ll mid = (l + r) / 2;
                int flag = check(L, mid, N);
                if(flag == 0)
                    return to_string(mid);
                else if(flag == 1)
                    l = mid + 1;
                else
                    r = mid - 1;
            }
            --L;
        }
        return to_string(-1);
    }

private:
    int check(int len, ll base, const ll N) {
        ll result = 1;
        ll p = 1;
        int l = 1;
        while(++l <= len)
        {
            p *= base;
            result += p;
            if(result > N)
                return -1;
            if(l < len && p > (N - result) / base)
                return -1;
        }
        if(result == N)
            return 0;
        return 1;
    }
};

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

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

注意:

  • 十六进制中所有字母(a-f)都必须是小写。
  • 十六进制字符串中不能包含多余的前导零。如果要转化的数为0，那么以单个字符’0’来表示；对于其他情况，十六进制字符串中的第一个字符将不会是0字符。
  • 给定的数确保在32位有符号整数范围内。
  • 不能使用任何由库提供的将数字直接转换或格式化为十六进制的方法。

示例 1：
输入:
26
输出:
“1a”

示例 2：
输入:
-1
输出:
“ffffffff”

算法

直接用以下方法将负数 num 转为无符号数 iter。原 32 位数的符号位的 1 是保留在 iter 中的。

1
unsigned int iter = num;

代码 (C++)

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
class Solution {
public:
    string toHex(int num) {
        if(num == 0) return "0";
        string result;
        int mask = (1 << 4) - 1;
        unsigned int iter = num;
        while(iter)
        {
            int d = iter & mask;
            result += int2ch(d);
            iter >>= 4;
        }
        reverse(result.begin(), result.end());
        return result;
    }

private:
    int int2ch(int x)
    {
        // 0 <= x <= 15
        if(x < 10)
            return '0' + x;
        x -= 10;
        return 'a' + x;
    }
};
Share