进制转换、编码与位运算

进制系统与位运算

开篇：成为一名真正的“数字建筑师”

我们将学习计算机的“母语”——二进制，探索它如何巧妙地表示所有数字（包括负数），并掌握一套能直接指挥CPU进行高效运算的“魔法指令”——位运算。

准备好了吗？让我们从理论到实践，从了解到精通，成为一名能搭建高效数字世界的“建筑师”！

第一部分：计算机的数字语言 (第一课时)

1.1 编码基础：C++中的多进制表示法

在C++代码中，我们可以直接写出不同进制的整数。为了让编译器能正确识别，需要使用特定的前缀。

二进制 (Binary): 以 0b 或 0B 开头。计算机的物理基础，由0和1组成。
八进制 (Octal):- 以 0 开头。在一些早期系统和文件权限表示中常用。
十六进制 (Hexadecimal): 以 0x 或 0X 开头。常用于表示内存地址、颜色代码等，是二进制的常用“简写”。

【代码示例 1-1：书写不同进制的数】

#include <iostream>
 
int main() {
    // 将十进制数 42 用不同进制表示
    int dec_num = 42;
    int bin_num = 0b101010;  // 32 + 8 + 2 = 42
    int oct_num = 052;       // 5*8 + 2 = 42
    int hex_num = 0x2A;      // 2*16 + 10 (A) = 42
 
    // std::cout 默认以十进制格式输出
    std::cout << "The value of 0b101010 is: " << bin_num << std::endl;
    std::cout << "The value of 052 is: " << oct_num << std::endl;
    std::cout << "The value of 0x2A is: " << hex_num << std::endl;
    
    return 0;
}

1.2 数据展示：格式化输入输出

<iomanip> 头文件提供了一系列工具，称为“流操纵符”，可以控制 cin 和 cout 的行为。

输出控制：
- std::dec: 设置 cout 以十进制输出（默认）。
- std::oct: 设置 cout 以八进制输出。
- std::hex: 设置 cout 以十六进制输出。
输入控制：
- cin >> hex >> num; 会让 cin 将用户的输入（如 “FF”）当作十六进制数来读取。

【代码示例 1-2：控制输入输出格式】

#include <iostream>
#include <iomanip> // 必须包含此头文件
 
int main() {
    int number = 100;
    std::cout << "Decimal " << number << " can be represented as:" << std::endl;
    std::cout << "  - Octal: " << std::oct << number << std::endl;       // 输出 144
    std::cout << "  - Hexadecimal: " << std::hex << number << std::endl; // 输出 64
 
    // 切换回十进制，否则后续输出都会是十六进制
    std::cout << std::dec; 
 
    int input_num;
    std::cout << "\nEnter a hexadecimal number (e.g., 1A): ";
    std::cin >> std::hex >> input_num; // 让cin按16进制读取
    std::cout << "You entered the decimal value: " << std::dec << input_num << std::endl;
 
    return 0;
}

1.3 核心算法：进制转换

A. 任意进制 → 十进制：“按权展开求和”

这是最基础、最通用的方法。一个R进制数的每一位都有一个“权重”，即 R 的幂。

【例题 1】 将十六进制 2B5 转换为十进制。

分析： 2B5 从右到左，第0位是5，第1位是B(11)，第2位是2。
计算： 5 * 16^0 + 11 * 16^1 + 2 * 16^2 = 5 * 1 + 11 * 16 + 2 * 256 = 5 + 176 + 512 = 693。

B. 十进制 → 任意进制：“除基取余，倒序排列”

反复用十进制数除以目标基数R，余数就是新进制的低位，商继续做下一次除法。

【例题 2】 将十进制 35 转换为二进制。

35 / 2 = 17 ... 1 (最低位)
17 / 2 = 8 ... 1
8 / 2 = 4 ... 0
4 / 2 = 2 ... 0
2 / 2 = 1 ... 0
1 / 2 = 0 ... 1 (最高位)
结果： 将余数倒序排列，得到 100011。

C. 信奥常用技巧：利用二进制作为“桥梁”

由于 8 = 2^3，16 = 2^4，所以二、八、十六进制之间可以快速转换。

技巧1：二进制 ↔ 十六进制 (四位一组)
- 【例题 3】(二转十六): 1110100110
  1. 分组 (从右向左，四位一组，不足补0): 0011 1010 0110
  2. 转换: 0011→3, 1010→A, 0110→6
  3. 结果: 0x3A6
技巧2：二进制 ↔ 八进制 (三位一组)
- 【例题 4】(二转八): 1110100110
  1. 分组 (从右向左，三位一组，不足补0): 001 110 100 110
  2. 转换: 001→1, 110→6, 100→4, 110→6
  3. 结果: 01646

第一课时 · 课后练习

基础题：
- 手动将十进制数 88 转换为二进制和十六进制。
- 手动将二进制数 10110101 转换为八进制和十六进制。
编程题： 编写一个程序，循环读取用户输入的十进制整数，然后输出其十六进制表示，直到用户输入0为止。
洛谷挑战 (入门)：
https://www.luogu.com.cn/problem/B3620
有用的函数stoi

第二部分：深入二进制世界 (第二课时)

2.1 设计的智慧：原码、反码与补码

计算机如何表示负数？这是一个伟大的设计。

原码 (Sign-Magnitude): 最直观的想法。最高位是符号位 (0正, 1负)。
- 缺陷： 有两个0 (+0和-0)，且加减法运算复杂。
反码 (One’s Complement): 负数是其正数形式的数值位按位取反。
- 缺陷： 仍然有两个0。
补码 (Two’s Complement): 现代计算机的标准方案。
- 规则： 正数三码合一。负数等于其反码+1。
- 优势：
  1. 唯一的0： 解决了+0/-0问题。
  2. 化减为加： a - b 可以用 a + (-b的补码) 实现，CPU只需要一个加法器。

【计算示例】 在8位系统中，计算 -18 的补码。

+18 的原码: 00010010
求反码 (符号位不变，数值位取反): 11101101
求补码 (反码 + 1): 11101101 + 1 = 11101110
- 因此，-18 在内存中就存储为 11101110。

2.2 效率之源：位运算符详解

位运算是直接在二进制位上进行的运算，速度极快。

运算符	名称	规则
`&`	按位与 (AND)	两位都为1，结果才为1。
\|	按位或 (OR)	只要有1位是1，结果就是1。
`^`	按位异或 (XOR)	两位不同为1，相同为0。
`~`	按位取反 (NOT)	0变1，1变0。作用于补码！
`<<`	左移	所有位向左移动n位，右侧补n个0。
`>>`	右移	所有位向右移动n位，左侧补n个0 (对正数)。

【代码示例 2-1：位运算演示】

#include <iostream>
#include <bitset> // 用于可视化二进制
 
int main() {
    int a = 60; // 0011 1100
    int b = 13; // 0000 1101
    
    std::cout << "a       = " << std::bitset<8>(a) << std::endl;
    std::cout << "b       = " << std::bitset<8>(b) << std::endl;
    std::cout << "a & b   = " << std::bitset<8>(a & b) << " (Decimal: " << (a & b) << ")" << std::endl;
    std::cout << "a | b   = " << std::bitset<8>(a | b) << " (Decimal: " << (a | b) << ")" << std::endl;
    std::cout << "a ^ b   = " << std::bitset<8>(a ^ b) << " (Decimal: " << (a ^ b) << ")" << std::endl;
    std::cout << "~a      = " << std::bitset<8>(~a) << " (Decimal: " << (~a) << ")" << std::endl;
    std::cout << "b << 2  = " << std::bitset<8>(b << 2) << " (Decimal: " << (b << 2) << ")" << std::endl;
    std::cout << "a >> 2  = " << std::bitset<8>(a >> 2) << " (Decimal: " << (a >> 2) << ")" << std::endl;
    return 0;
}

2.3 应用实践：位运算的常见技巧

技巧1：快速乘除 2 的幂
- x * 8 等同于 x << 3
- x / 4 等同于 x >> 2
技巧2：判断奇偶
- if (x & 1): 如果为真，x是奇数。
- if (!(x & 1)): 如果为真，x是偶数。

技巧3：无临时变量交换两数 (一个经典的面试题)

int a = 10, b = 20;
a = a ^ b;
b = a ^ b; // b 变回了原来的 a
a = a ^ b; // a 变回了原来的 b

技巧4：状态压缩 (Bitmask)
- 场景： 有8盏灯，编号0-7。我们可以用一个unsigned char (8位)来表示所有灯的状态。
- 检查第3盏灯是否亮: if (status & (1 << 3))
- 点亮第5盏灯: status |= (1 << 5)
- 熄灭第2盏灯: status &= ~(1 << 2)
- 切换第1盏灯的状态: status ^= (1 << 1)

第二课时 · 课后练习

基础题：
- 100 & 50 的十进制结果是多少？
- 100 | 50 的十进制结果是多少？
- 100 ^ 50 的十进制结果是多少？
编程题： 编写一个程序，输入一个正整数，输出它二进制表示中 1 的个数。（提示：可以用 n & (n - 1) 这个操作，它每次都能消除掉二进制中最右边的那个1，循环直到n为0，看循环了多少次）。
洛谷挑战 (入门)：
- P5705 【深基2.例7】数字反转
  - 这道题本身不难，是用字符串处理。但你可以挑战一下自己，能否用纯数学方法（%和/）实现？这和我们“除基取余”的思想异曲同工，是很好的基础数论和逻辑练习。
- B2029 大象喝水
  - 非常简单的数学题，但可以思考一下，如果水桶容量是2的幂，比如16升，我们能不能用位运算来快速计算？这有助于你建立将常规运算与位运算联系起来的思维。

信奥讲义知识库

探索