进制与位运算

一、数的进制概念

1.1 什么是进制

进制是一种计数方式，核心规则是 “逢 N 进一”。

一个进制由两个要素决定：

1.2 常用进制

（1）十进制（Decimal）

• 基数：10
• 数码：0 1 2 3 4 5 6 7 8 9
• 规则：逢十进一
• 例：9 + 1 = 10（个位满 10，向十位进 1）

（2）二进制（Binary）

• 基数：2
• 数码：0 1
• 规则：逢二进一
• 例：1 + 1 = 10（读作"一零"，不读"十"）
• 计算机采用二进制的原因：电子元件只有"通电/断电"、"高电平/低电平"两种稳定状态，天然对应 1 和 0。

（3）八进制（Octal）

• 基数：8
• 数码：0 1 2 3 4 5 6 7（没有 8 和 9）
• 规则：逢八进一
• 例：7 + 1 = 10（八进制的 10 等于十进制的 8）

（4）十六进制（Hexadecimal）

• 基数：16
• 数码：0 1 2 3 4 5 6 7 8 9 A B C D E F
• 规则：逢十六进一

十六进制需要 16 个数码，但阿拉伯数字只有 0~9 共 10 个，不够用，于是借用英文字母补齐后 6 个：

字母可以大写也可以小写，FF 与 ff 等价。

（5） N 进制

既然十六进制能用字母表示超过 9 的数码，那么继续往下推：

• 二十进制需要数码 0~9, A~J
• 三十六进制需要数码 0~9, A~Z（正好用完 26 个字母，这是常见进制的上限）

由此，通用的 N 进制概念：

N 进制：有 N 个数码（0, 1, ..., N-1，超过 9 的部分用 A, B, C... 依次表示），逢 N 进一，第 i 位的位权为 N^i。

1.3 进制的书写标识

为避免歧义，需要标明数字属于哪种进制：

⚠️ 注意：C++ 中以 0 开头的整数字面量是八进制。写 int x = 017; 实际上 x 等于 15，不是 17。

---

二、整数：十进制转 N 进制

2.1 方法：除 N 取余，逆序排列

步骤：

1. 用十进制数除以 N，记下商和余数；
2. 用商继续除以 N，再记余数；
3. 重复直到商为 0；
4. 把所有余数**从下往上（逆序）**排列，即为结果。

口诀：除 N 取余，倒序读数。

2.2 例题演示

例 1：把十进制 45 转为二进制

45 ÷ 2 = 22 ... 余 1   ↑
22 ÷ 2 = 11 ... 余 0   ↑
11 ÷ 2 =  5 ... 余 1   ↑ 逆序  
 5 ÷ 2 =  2 ... 余 1   ↑ 读取  
 2 ÷ 2 =  1 ... 余 0   ↑ 
 1 ÷ 2 =  0 ... 余 1   ↑

结果：(45)₁₀ = (101101)₂

验算：32 + 8 + 4 + 1 = 45 ✔

例 2：把十进制 45 转为八进制

45 ÷ 8 = 5 ... 余 5 
5 ÷ 8 = 0 ... 余 5

结果：(45)₁₀ = (55)₈

例 3：把十进制 255 转为十六进制

255 ÷ 16 = 15 ... 余 15 → F 
15 ÷ 16 =  0 ... 余 15 → F

结果：(255)₁₀ = (FF)₁₆

余数大于 9 时，必须换成对应字母，不能直接写数字。

---

三、小数：十进制与二进制互转

3.1 十进制小数 → 二进制

方法：乘 2 取整，顺序排列

步骤：

1. 把小数部分乘以 2，取出结果的整数部分（0 或 1）作为二进制小数的一位；
2. 用剩下的小数部分继续乘 2；
3. 重复，直到小数部分为 0，或达到所需精度；
4. 把取出的整数位**从上往下（顺序）**排列。

口诀：乘 2 取整，正序读数。

例 1：十进制0.625 转二进制

0.625 × 2 = 1.25  → 取整 1   ↓
0.25  × 2 = 0.5   → 取整 0   ↓ 顺序  
0.5   × 2 = 1.0   → 取整 1   ↓ 读取  
小数部分为 0，结束  

结果：(0.625)₁₀ = (0.101)₂

例 2：十进制0.1 转二进制（无限循环）

0.1 × 2 = 0.2 → 0  
0.2 × 2 = 0.4 → 0  
0.4 × 2 = 0.8 → 0  
0.8 × 2 = 1.6 → 1  
0.6 × 2 = 1.2 → 1  
0.2 × 2 = 0.4 → 0   ← 开始循环  
...  

结果：(0.1)₁₀ = (0.0001100110011...)₂ = (0.0 0011̇ 0011̇...)₂

结论：十进制小数不一定能用有限位二进制精确表示。
这就是程序中 0.1 + 0.2 != 0.3 的根本原因，也是浮点数不能用 == 直接比较的原因。
二进制小数只需要求出需要的位数即可`。

---

四、整数：N 进制转十进制（位权法）

4.1 位权的概念

位权： 在 N 进制数中，从右往左数（右起为第 0 位），第 i 位的位权 = N^i。

以十进制 3567 为例，直观理解位权：

3    5    6    7  
│    │    │    └── 个位：7 × 10⁰ = 7  
│    │    └─────── 十位：6 × 10¹ = 60  
│    └──────────── 百位：5 × 10² = 500  
└───────────────── 千位：3 × 10³ = 3000  
  合计 = 3567

4.2 转换公式

口诀：按权展开，相加求和。

4.3 案例演示

例 1：(1101)₂ → 十进制

1×2³ + 1×2² + 0×2¹ + 1×2⁰  
= 8 + 4 + 0 + 1  
= 13  

例 2：(345)₈ → 十进制

3×8² + 4×8¹ + 5×8⁰  
= 3×64 + 4×8 + 5  
= 192 + 32 + 5  
= 229  

例 3：(2AF)₁₆ → 十进制

2×16² + A×16¹ + F×16⁰  
= 2×256 + 10×16 + 15×1  
= 512 + 160 + 15  
= 687  

字母数码要先换成对应的十进制值（A=10 … F=15）再计算。

五、二、八、十六进制互转

5.1 原理：为什么可以"打包"转换

因为 8 = 2³、16 = 2⁴，所以：

• 1 位八进制 恰好对应 3 位二进制
• 1 位十六进制 恰好对应 4 位二进制

这使得转换可以直接分组替换，不需要经过十进制中转。

5.2 二进制 ↔ 八进制：三位一体、421 法

（1）421 法

3 位二进制的位权从左到右是 4 2 1：

二进制:  1  0  1  
位权:    4  2  1  
计算:    4 + 0 + 1 = 5  

记住 421 三个数，看到 1 就把对应位权加起来，速度极快。

对照表：

（2）二进制 → 八进制

规则：整数部分从右往左、小数部分从左往右，每 3 位一组，不足高位补 0。

例：(10110101)₂ → 八进制

原数:        10110101  
从右往左分组: 010 110 101   ← 最左边不足 3 位，补一个 0
421 法:       2   6   5  

结果：(10110101)₂ = (265)₈

（3）八进制 → 二进制

规则：一位拆三位（三位一体），高位的多余 0 可以去掉。

例：(507)₈ → 二进制

5 → 101  
0 → 000  
7 → 111  

结果：(507)₈ = (101000111)₂

5.3 二进制 ↔ 十六进制：四位一体、8421 法

（1）8421 法

4 位二进制的位权从左到右是 8 4 2 1：

二进制:  1  1  0  1  
位权:    8  4  2  1  
计算:    8 + 4 + 0 + 1 = 13 → D  

对照表：

（2）二进制 → 十六进制

规则：整数部分从右往左、小数部分从左往右，每4位一组，不足高位补 0。

例：(1101101011)₂ → 十六进制

原数:        1101101011  
从右往左分组: 0011 0110 1011   ← 左边补 2 个 08421 法:      3    6    B  

结果：(1101101011)₂ = (36B)₁₆

（3）十六进制 → 二进制

规则：一位拆四位（四位一体）。

例：(A5F)₁₆ → 二进制

A → 1010  
5 → 0101  
F → 1111  

结果：(A5F)₁₆ = (101001011111)₂

5.4 八进制 ↔ 十六进制：以二进制为桥梁

八进制和十六进制不能直接分组转换（因为 8 不是 16 的幂），必须先转成二进制再重新分组。

八进制 ──1位拆3位──> 二进制 ──4位一组──> 十六进制  
十六进制 ──1位拆4位──> 二进制 ──3位一组──> 八进制  

例 1：(756)₈ → 十六进制

第一步（拆 3 位）：  
 7 → 111,  5 → 101,  6 → 110  得到：111101110  
  
第二步（重新按 4 位分组，左边补 0）：  
 0001 1110 1110  
第三步（8421 法）：  
 1    E    E

结果：(756)₈ = (1EE)₁₆

例 2：(2D)₁₆ → 八进制

第一步（拆 4 位）：  
 2 → 0010,  D → 1101  得到：00101101  
  
第二步（重新按 3 位分组，左边补 0）：  
 000 101 101  
第三步（421 法）：  
 0   5   5  
去掉前导 0

结果：(2D)₁₆ = (55)₈

5.5 转换方法速查

---

六、位运算：基于二进制逐位计算

6.1 概述

位运算直接对整数在内存中的二进制位进行操作，逐位独立计算。

特点：

• 快：位运算是 CPU 的原生指令，比乘除法快得多；
• 省：可以用一个整数的每一位表示一个状态（状态压缩）。

C++ 中共有 6 种位运算符：

6.2 按位与 &

口诀：同 1 为 1，有 0 则 0（也可记作"全 1 才 1"）

真值表：

计算示例：12 & 10

 12 → 1100 
 10 → 1010 
 ------------ 
    & 1000  → 8

常见用途：

// 1. 判断奇偶：比 n % 2 更快  
if (n & 1) cout << "奇数";  
  
// 2. 取出某一位（第 k 位，从 0 开始）  
int bit = (n >> k) & 1;  
  
// 3. 清零某一位  
n = n & ~(1 << k);  
  
// 4. 取低 k 位  
int low = n & ((1 << k) - 1);  
  
// 5. 判断是否为 2 的幂  
bool isPow2 = (n > 0) && ((n & (n - 1)) == 0);  
  
// 6. lowbit：取出最低位的 1（树状数组核心）  
int lowbit = n & (-n);  

6.3 按位或 |

口诀：同 0 为 0，有 1 则 1（也可记作"全 0 才 0"）

真值表：

计算示例：12 | 10

 12 → 1100 
 10 → 1010 
 ------------ 
    | 1110  → 14

常见用途：

// 1. 把第 k 位置为 1n = n | (1 << k);  
  
// 2. 合并两个状态集合  
int merged = stateA | stateB;  

6.4 按位异或 ^

口诀：相同为 0，相异为 1（也叫"不进位加法"）

真值表：

计算示例：12 ^ 10

 12 → 1100 
 10 → 1010 
 ------------ 
     ^ 0110  → 6

重要性质：

常见用途：

// 1. 翻转第 k 位  
n = n ^ (1 << k);  
  
// 2. 不用临时变量交换两数（利用自反性）  
a ^= b;  b ^= a;  a ^= b;  
  
// 3. 找出只出现一次的数（其余都出现两次）  
int single = 0;  
for (int x : arr) single ^= x;   // 成对的数互相抵消  

6.5 按位取反 ~

口诀：0 变 1、1 变 0（单目运算符，只需要一个操作数）

计算示例（以 8 位为例）：

 5 → 0000 0101 
 ~5 → 1111 1010  
 → 补码表示，值为 -6

重要规律：在补码表示下，

~n = -n - 1  

例：~5 = -6，~0 = -1，~(-1) = 0

⚠️ 注意区分 ~ 和 !

• ~ 是按位取反，逐位翻转，结果是整数：~5 = -6
• ! 是逻辑非，结果只有 0 或 1：!5 = 0

6.6 四种基本位运算对比

以 a = 12 (1100)，b = 10 (1010) 为例：

---

七、移位运算

7.1 格式

原数 + 移位符号 + 移动的位数  

例如：a << 2 表示把 a 的二进制位整体向左移动 2 位。

7.2 左移 <<

规则：所有二进制位向左移动，右边空出的位补 0，左边移出的位丢弃。

示例：5 << 1

 5  → 0000 0101
 5 << 1 
 → 0000 1010  
 → 10  

规律：

左移 1 位相当于乘以 2；左移 n 位相当于乘以 2ⁿ。

a << 1  ==  a * 2  
a << 2  ==  a * 4  
a << 3  ==  a * 8  
a << n  ==  a * 2ⁿ  

常用技巧：

1 << 0  = 1  
1 << 1  = 2  
1 << 2  = 4  
1 << 10 = 1024        // 1K  
1 << 20 = 1048576     // 1M  
1 << 30 = 1073741824  // 约 1e9，常用作 INF  

⚠️ 溢出风险：int 是 32 位，1 << 31 会溢出变成负数。
需要大数时要写 1LL << 40，先转成 long long 再移位。

7.3 右移 >>

规则：所有二进制位向右移动，右边移出的位直接丢弃（不是四舍五入）。

示例：10 >> 1

 10  → 0000 1010
 10 >> 1 
 → 0000 0101  
 → 5  

规律：

右移 1 位相当于除以 2（整除）；右移 n 位相当于除以 2ⁿ。

a >> 1  ==  a / 2  
a >> 2  ==  a / 4  
a >> n  ==  a / 2ⁿ  

注意取整方向：

 7 >> 1 =  3    // 7 / 2 = 3.5，舍去小数  
 9 >> 2 =  2    // 9 / 4 = 2.25，舍去小数  
-7 >> 1 = -4    // 算术右移向下取整，而 -7 / 2 = -3（向零取整）  

⚠️ 负数的右移与除法结果可能不同：
>> 对负数是向下取整（向 -∞），而 / 是向零取整。
所以对可能为负的数，不要用 >> 替代 / 2。

7.4 移位的常见应用

// 1. 生成第 k 位为 1 的掩码  
int mask = 1 << k;  
  
// 2. 生成低 k 位全为 1 的掩码  
int mask = (1 << k) - 1;  
  
// 3. 取出 n 的第 k 位  
int bit = (n >> k) & 1;  
  
// 4. 二分查找的中点（防溢出写法）  
int mid = l + ((r - l) >> 1);  
  
// 5. 遍历一个数的所有二进制位  
for (int i = 0; i < 32; i++)  
	 cout << ((n >> i) & 1);  
// 6. 枚举集合 S 的所有子集（状压 DP）  
for (int sub = S; sub; sub = (sub - 1) & S) { /* ... */ }  

---