我的算法书 - 进制转换

一句话算法

进制转换就是反复回答两个问题：每一位的权值是多少，以及当前最低位是多少。

问题模型

一个整数可以用不同进制表示。

十进制是“逢十进一”。
二进制是“逢二进一”。
$k$ 进制是“逢 $k$ 进一”。

例如二进制数 1101 表示：

1\times 2^3+1\times 2^2+0\times 2^1+1\times 2^0=13

本文重点讨论两个基础问题：

给定二进制字符串，求它对应的十进制整数。
给定十进制整数，求它的二进制表示。

这两个问题掌握以后，推广到任意 $k$ 进制只是把基数 2 换成 k。

核心直觉

位权

在十进制中，123 的含义是：

1\times 10^2+2\times 10^1+3\times 10^0

在二进制中，1101 的含义是：

1\times 2^3+1\times 2^2+0\times 2^1+1\times 2^0

所以一个 $k$ 进制数：

a_m a_{m-1}\cdots a_1 a_0

表示的十进制值是：

a_m k^m+a_{m-1}k^{m-1}+\cdots+a_1k+a_0

其中每一位 $a_i$ 都满足 $0\le a_i<k$ 。

从左到右累加

把二进制 1101 从左到右读：

0
1
1 * 2 + 1 = 3
3 * 2 + 0 = 6
6 * 2 + 1 = 13

每读入一位，就让当前值乘以基数，再加上这一位：

ans = ans \times 2 + digit

从低位往高位拆

十进制转二进制时，最低位最容易得到：

偶数的二进制最低位是 0。
奇数的二进制最低位是 1。

所以最低位就是：

n\bmod 2

取出最低位后，用整除删除最低位：

n \leftarrow \lfloor n/2 \rfloor

不断重复，直到 $n=0$ 。因为先得到的是低位，所以最后要反转。

算法步骤

二进制转十进制

令 ans = 0。
从左到右扫描二进制字符串。
对每个字符 ch，令 digit = ch - '0'。
更新 ans = ans * 2 + digit。
扫描结束后，ans 就是十进制值。

十进制转二进制

若 n == 0，答案是 "0"。
当 n > 0：
- 记录最低位 n % 2。
- 删除最低位 n /= 2。
反转记录到的所有位。

算法证明

二进制转十进制

核心不变量：扫描到当前位置后，ans 等于已经读过的前缀所表示的十进制值。

假设已经读过的前缀值为 $x$ 。下一位是 $d$ ，新的前缀相当于把原来的所有位左移一位，再把最低位填成 $d$ ：

x \Rightarrow 2x+d

代码中的更新：

ans = ans \times 2 + d

正好完成这个变化。因此扫描结束时，ans 就是整个二进制串的值。

十进制转二进制

核心不变量：每一步都正确取出当前二进制表示的最低位。

任意非负整数 $n$ 都可以写成：

n = 2q + r

其中 $r\in\{0,1\}$ 。

$r=n\bmod 2$ ，它就是二进制最低位。
$q=\lfloor n/2\rfloor$ ，它就是删除最低位后剩下的数。
对 $q$ 重复同样过程，就能依次得到所有位。

因为得到顺序是从低位到高位，所以最后反转后得到正确二进制表示。

复杂度分析

设输入数字的二进制长度为 $L$ 。

二进制转十进制：时间复杂度 $O(L)$ ，空间复杂度 $O(1)$ 。
十进制转二进制：时间复杂度 $O(L)$ ，空间复杂度 $O(L)$ ，用于保存答案字符串。

如果结果可能超过 long long，需要使用高精度整数或直接在字符串上处理。

代码实现

二进制转十进制

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

        #include <bits/stdc++.h>
using namespace std;

// 把二进制字符串转成十进制整数。
// 例: "1101" -> 13
long long bin2dec(const string& s) {
    long long ans = 0;
    for (char ch : s) {
        ans = ans * 2 + (ch - '0');
    }
    return ans;
}

int main() {
    string s;
    cin >> s;
    cout << bin2dec(s) << "\n";
    return 0;
}

十进制转二进制

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

        #include <bits/stdc++.h>
using namespace std;

// 把非负十进制整数转成二进制字符串。
// 例: 13 -> "1101"
string dec2bin(long long n) {
    if (n == 0) return "0";

    string ans;
    while (n > 0) {
        ans.push_back(char('0' + n % 2));
        n /= 2;
    }
    reverse(ans.begin(), ans.end());
    return ans;
}

int main() {
    long long n;
    cin >> n;
    cout << dec2bin(n) << "\n";
    return 0;
}

测试用例

二进制转十进制：

输出：

十进制转二进制：

输出：

边界情况：

十进制转二进制输出：

应用分类详解

进制转换的本质是：用“位”和“权值”描述整数。只要问题涉及二进制状态、位运算、数字拆分、字符串表示，就应该想到进制模型。

一、数字表示转换

典型模式： 题目直接要求把一个数从一种进制转成另一种进制。

识别信号： 出现“二进制”“八进制”“十六进制”“base”“进制转换”。

核心建模： 先转成十进制理解数值，再按目标进制不断取模和整除。

应用场景	经典题目	核心思路
基础进制转换	roj-8006	字符串读入，按位权累加
目标进制输出	roj-8008	不断对目标基数取模

二、位运算与二进制状态

典型模式： 每一位只有 0/1 两种状态，整体状态可以压成一个整数。

识别信号： 出现“开/关”“选/不选”“集合子集”“状态压缩”。

核心建模： 第 $i$ 位表示第 $i$ 个对象是否被选择。检查一位用 x >> i & 1，打开一位用 x | (1 << i)。

应用场景	经典题目	核心思路
子集枚举	luogu-P1157	用二进制位表示每个元素选或不选
状压 DP	luogu-P1896	用整数保存一行或一个集合的状态

三、拆数字与逐位处理

典型模式： 需要从低位到高位检查数字的每一位。

识别信号： 出现“每一位”“数位”“各位数字”“二进制中 1 的个数”。

核心建模： 用 n % base 取最低位，用 n /= base 删除最低位。

应用场景	经典题目	核心思路
统计二进制 1 的个数	LeetCode 191	不断检查最低位或使用 `n & (n - 1)`
数位处理	luogu-P1307	反复取模拆出十进制位

四、高精度与大整数输入

典型模式： 数字太大，无法直接放进整数类型。

识别信号： 输入是长字符串，位数可能达到几百、几千甚至更多。

核心建模： 把字符串当作“位数组”，按进制规则模拟乘法、加法、除法。

应用场景	经典题目	核心思路
大整数进制转换	luogu-P1143	字符串转值或模拟短除法
高精度运算	luogu-P1601	每一位作为数组元素参与计算

经典例题

1. roj-8006

基础进制转换题。重点是理解“当前答案乘以基数再加当前位”的过程。

2. luogu-P1143

给定原进制和目标进制，完成一般进制转换。字符位可能包含 A-F，需要写好字符和数值之间的映射。

3. luogu-P1896

状压 DP 题。二进制不是为了输出，而是用来压缩集合状态，每一位代表某个位置是否放置。

参考

旧版文章：Rbook_ejs_old/book/math/number_base/index.md