进制转换与位运算
整数之间的进制转换¶
十进制转其他进制（除基取余法）
步骤：对 $N$ 不断做
记录余数 $r$，然后令 $N \leftarrow q$；当 $N=0$ 时，把余数逆序拼回即为目标进制表示。
示例（完整步骤）：把 $123_{10}$ 转为二进制
代码实现
// 十进制 n 转 b 进制的自定义函数
// 时间复杂度：O(logn)
string f(int n, int b)
{
string s;
while (n != 0)
{
int r = n % b;
if (r < 10)
s += char(r + 48);
else
s += char(r + 55);
n = n / b;
}
reverse(s.begin(), s.end());
return s;
}
其他进制转十进制（按位相加）
若一个数在进制 $b$ 下的位串为 $d_k d_{k-1}\dots d_1 d_0$，则它在十进制的值为
把每位乘以其位权再相加。
示例：$\text{0x3F}$（十六进制）转换为十进制：
代码实现如下
// b 进制的 s 转 10 进制的自定义函数
string f(string s, int b)
{
long long sum = 0;
for (int i = 0; i < s.size(); i++)
{
int d = 0;
if (s[i] <= '9')
d = s[i] - 48;
else
d = s[i] - 55;
sum = sum * b + d;
}
return sum;
}
例题题目：把 $2025_{10}$ 转成二进制（写出完整结果）。📝
解析（逐步拆解）：
把 $2025$ 用 2 的幂拆分（写出从大到小的位权）：
选取能相加到 $2025$ 的幂：
对应位（从 $2^{10}$ 到 $2^0$）为：$1,1,1,1,1,1,0,1,0,0,1$，所以
答案：$11111101001_2$ ✅
进制字面量标记法
在 C/C++ 里，不同进制的数有不同的写法：
- 二进制 bin：前缀
0b。例如：0b1001 = 9₁₀ - 八进制 oct：前缀
0。例如：0123 = 83₁₀（⚠️ 不是 $123$ 十进制！） - 十进制 dec：直接写数字。例如：
123 = 123₁₀ - 十六进制 hex：前缀
0x。例如：0x3f = 63₁₀
📌 英文缩写对照
- bin（二进制）
- oct（八进制）
- hex（十六进制）
示例代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
cout << 0b1001 << "\n"; // 二进制，9
cout << 123 << "\n"; // 十进制，123
cout << 0123 << "\n"; // 八进制，83
cout << 0x3f << "\n"; // 十六进制，63
}
二/八/十六之间的便捷转换¶
目标：在考试中快速实现二进制与十六进制，二进制与八进制互转（不包括八进制与十六进制互转），不必每次先转到十进制。
核心规则
- 每一位十六进制（hex）对应 $4$ 位二进制：
$$ 1\ \text{hex digit} \iff 4\ \text{binary bits}. $$
- 每一位八进制（oct）对应 $3$ 位二进制：
$$ 1\ \text{octal digit} \iff 3\ \text{binary bits}. $$
做法：把二进制从低位向高位每 $4$ 或 $3$ 位分组，不足位在高位用 $0$ 补齐，然后逐组替换为 十六进制或八进制 的数字。
练习 1
把 $\text{0x7B}$ 转成二进制：
通常去掉高位的前导 $0$，写作 $1111011_2$。
练习 2
把 $\text{0xA3F}$ 转为二进制和八进制。📝
解析：
- 先 十六进制转二进制：
$A=1010,\quad 3=0011,\quad F=1111$
所以
$$ \text{0xA3F} = 1010\ 0011\ 1111_2 = 101000111111_2. $$
- 二进制转八进制：从右向左每 $3$ 位分组（不足高位补 $0$）：
$$ 101\ 000\ 111\ 111 \Rightarrow 5\ 0\ 7\ 7 \Rightarrow 5077_8. $$
答案：$101000111111_2,\quad 5077_8$ ✅
小数部分的进制转换¶
二进制小数转十进制
例如二进制小数 $1010.01_2$ 转为十进制：
其转换规则同整数部分，区别仅仅在于需要累加小数部分的权重。即：
$a^{-b}=\frac{1}{a^b}$
其余进制小数转十进制以此类推。
十进制小数转二进制
例如十进制小数 $0.25$ 转为二进制：
方法：乘 $2$ 取整法，直到小数部分为 $0$ 停下。
小数部分为 $0$ 结束。
整数部分 正序排列。因此十进制小数 $0.25$ 的二进制为 $0.01_2$。
但有些十进制小数没有精确的二进制表示请看下面示例。
示例（有限情况）
把 $0.625_{10}$ 转为二进制：
因此 $0.625_{10}=0.101_2$（有限）。
示例（循环情况）
把 $0.1_{10}$ 转为二进制（前若干位）：
得到循环节，前 $12$ 位为
因此 $0.1_{10}$ 在二进制下是 无限循环 的。
十进制小数转其余进制以此类推。
原码、反码、补码¶
在进行位运算前，我们需要理解计算机中数值的二进制表示方式：
1. 原码（Sign-Magnitude）
- 正数的原码就是其二进制形式。加一个符号位（最高位为 $0$）
- 负数的原码是其二进制，加一个符号位（最高位为 $1$）。
例如：
+1的原码：$\textcolor{red}00000000\ 0000000\ 00000000 \ 00000001$-1的原码：$\textcolor{red}10000000\ 0000000\ 00000000 \ 00000001$
2. 反码（Ones' Complement）
- 正数的反码与原码相同。
- 负数的反码是对其原码除符号位外的每一位取反。
例如：
+1的反码：$\textcolor{red}00000000\ 00000000\ 00000000 \ 00000001$-1的反码：$\textcolor{red}11111111\ 11111111\ 11111111 \ 11111110$
3. 补码（Two's Complement）
- 正数的补码仍与原码相同。
- 负数的补码 = 反码 $+ 1$。
例如：
+1的补码：$\textcolor{red}00000000\ 00000000\ 00000000 \ 00000001$-1的补码：$\textcolor{red}11111111\ 11111111\ 11111111 \ 11111111$
计算机中 所有数值的存储与计算 都使用 补码。
位运算¶
按位与：&
定义：对应位都为 $1$ 时结果位为 $1$，否则为 $0$。常用于掩码（取位）。
性质：
- $a\&b = b\&a$ （交换律）
- $a\&a=a$
示例：$5\&3$
示例：$-5\&-3$
注意负数要算出补码后计算。
最后的计算结果也为补码，如果需要求出十进制下的结果，需要将 $11111001_2$ 转回原码可以得到是 $10000111_2=-7_{10}$。
经典应用
n >> i & 1可以判断 $n$ 的二进制第 $i$ 位是否为 $1$。- 注意二进制下称最低为通常为第 $0$ 位。
按位或：|
定义：对应位任一为 $1$ 时结果位为 $1$。常用于置位。
性质：
- $a|b=b|a$
- $a|a=a$
示例：$5|2$
示例：$-5|-3$
注意负数要算出补码后计算。
最后的计算结果也为补码，如果需要求出十进制下的结果，需要将 $11111111_2$ 转回原码可以得到是 $10000001_2=-1_{10}$。
异或：^（XOR）
定义：对应位相异时为 $1$，相同时为 $0$。常用于切换/无进位相加。
性质：
- $x\oplus x = 0$
- $x\oplus 0 = x$
- 具有交换和结合律。
- 异或的数学符号是 $\oplus$
示例：$5\oplus3$
示例：$-5\oplus -3$
注意负数要算出补码后计算。
最后的计算结果也为补码，如果需要求出十进制下的结果，需要将 $00000110_2$ 转回原码（正数原反补均相同）可以得到是 $00000110_2=6_{10}$。
取反：~
定义：按位取反（0↔1）。在计算机中通常基于二补码，其数值关系为：
注意：取反结果受位宽影响（例如 $8$ 位、$32$ 位等）。
示例（$8$-bit，无符号解释）：
练习
- 题：在 8-bit 下，$x=150$，求 $\sim x$ 的无符号结果。
- 解：$150=10010110_2$，取反得 $01101001_2=105$。
- 答：$105$（无符号）。
左移：<<
意义：把位向左移动，低位补 $0$。在不溢出的情况下，等价于乘以 $2^k$：
注意：对负数或移位超出位宽，在 C/C++ 中可能 未定义。
练习
- 题：$1<<3$ 等于多少？
- 答：$8$（因 $1\times2^3=8$）。
通常使用
1 << n快速获取 $2^n$。但要注意溢出问题。
右移：>>
意义：把位向右移动。对无符号数是逻辑右移（高位补 $0$），对有符号数很多实现做算术右移（高位补符号位），近似等价于整除 $2^k$：
注意：带符号右移是否补符号位取决实现，不要在考试代码题中依赖未定义行为。
通常使用
a + b >> 1代替(a + b) / 2。
总结¶
所有的位运算计算都是用 补码 计算。
| 运算符 | 名称 | 描述 | 示例（按位） |
|---|---|---|---|
& |
与 | 同为 $1$ 结果为 $1$ | 1101 & 1011=1001 |
| |
或 | 有 $1$ 则为 $1$ | 1101 | 1011 = 1111 |
^ |
异或 | 相同为 $0$ 不同为 $1$ | 1101 ^ 1011 = 0110 |
~ |
取反 | 所有位翻转 | ~1101 = 0010（按位） |
<< |
左移 | 所有位左移 $n$ 位，低位补 $0$ | 0001 << 2 = 0100 |
>> |
右移 | 所有位右移 $n$ 位，高位补符号位（有符号）或 $0$（无符号） | 1000 >> 2 = 0010（无符号） |
位运算常见技巧与应用¶
取第 $i$ 位 —— (n >> i) & 1
含义：把 $n$ 二进制第 $i$ 位右移到最低位，再与 $1$ 按位与，得到 $0$ 或 $1$。
示例：令 $n=13$，求第 $2$ 位（最低位称之为第 $0$ 位）：
- $13=1101_2,\quad (13>>2)=11_2=3,\quad 3\&1=1$，所以第 $2$ 位为 $1$。
取最低位的 1（lowbit） —— x & -x
含义：表达式 x & -x 返回 $x$ 中最低位的 $1$ 对应的 值（例如 $4$、$8$ 等）。
原理（直观）：在二补码下 $-x = \overline{x}+1$，与 $x$ 按位与只保留最低的 1。
注意负数要算出补码后在计算。熟知本技巧含以后就可以直接利用 $x$ 的二进制求得结果。
示例：$x=12=1100_2$，则
清除最低位的 1 —— x & (x - 1)
含义：表达式 x & (x - 1) 将把 $x$ 的最低位的 $1$ 变为 $0$，其余位不变。常用于计数二进制下 $1$ 的个数。
例子：$x=12=1100_2$，
应用：计算 $x$ 二进制下 $1$ 的个数的一种写法，时间复杂度也是 $O(\log{x})$。
int count(int x) // 求二进制下有几个 1
{
int cnt = 0;
while (x)
{
x &= x - 1;
++cnt;
}
return cnt;
}
判断 $x$ 是否为 $2$ 的幂
公式：
（因为 $2$ 的幂在二进制中只有一个 $1$。）
练习
- 题：$x=16$，判断是否为 2 的幂？
- 解：$16\&(16-1)=16\&15=0$，且 $x>0$，所以是。
- 答：是（$\text{True}$）。✅
统计 1 的个数（popcount）
方法：使用内置函数（如 GNU C++ 的 __builtin_popcount(x)）或循环 x &= x - 1 或直接数位拆分。
int count(int x)
{
int cnt = 0;
while (x)
{
if (x % 2 == 1) cnt++;
x /= 2;
}
return cnt;
}
其余知识点总结¶
基本存储单位
- 位：bit。
- 字节：byte。
1 byte = 8 bit- byte 也可以用 B 表示
- 千字节：KB。
1 KB = 1024 B（不是 $1000$） 1 MB = 1024 KB = 1024 × 1024 B = 1,048,576 B1 GB = 1024 MB
记忆技巧：计算机中的“千”通常是 $2$ 的幂（$1024 = 2^{10}$）。
字节是计算机内存的基本单位，而位是计算机运算的最小单位。
常见 C/C++ 基本类型内存的占用
char：$1$ 字节short：$2$ 字节int：$4$ 字节long long：$8$ 字节float：$4$ 字节double：$8$ 字节bool：$1$ 字节
数组内存的计算方法
计算数组/变量占用内存的基本思路：元素数量 × 每元素字节数 = 总字节数，再除以 $1024$ 或 $1024^2$ 转成 KB / MB。
例子：
int a[100]：100 × 4 = 400 B- =
400 / 1024 ≈ 0.390625 KB - =
400 / 1024 / 1024 ≈ 0.00038147 MB（非常小）
- =
int a[1000_000]：1,000,000 × 4 = 4,000,000 B- $\approx$
3.814697265625 MB
- $\approx$
long long b[1000000]：1,000,000 × 8 = 8,000,000 B- $\approx$
7.62939453125 MB
- $\approx$
常见导致 MLE 的坑
- 不要在栈上开超大数组（如
int a[10000000];可能栈溢出）。栈通常只有几 MB（视系统/判题机而定）。- 推荐：把大数组声明为全局变量。
- 全局变量开了超大的数组，例如
int a[1000000000]大约需要 $3814$ MB 的内存。或者开了int a[100000][100000]超大的二维数组爆内存。 - 使用合适的数据类型：
- 不需要
long long就别用，int（4B）比long long（8B）省内存。
- 不需要
不同类型的取值范围
示例： int 的大小
int占 4 字节 = 32 位。
C/C++ 中的 int 默认是 有符号的，使用 补码表示。
-
最高位（第 $31$ 位）是符号位：
-
0表示正数 1表示负数- 正数：二进制与无符号相同。
- 负数：其补码 = 对应正数按位取反 $+ 1$。
正数范围
- 最高位为
0，剩下 $31$ 位用于表示数值。 - 最大值：
0111...111（$31$ 个 $1$）
负数范围
- 最小值：
1000...000（符号位 $1$，其他全 $0$）
int 总结范围
- 最小值：-2,147,483,648
- 最大值：2,147,483,647
所以：
无符号 unsigned int
- 也是 $4$ 字节 = $32$ 位。
- 范围：
小扩展
short（$2$ 字节 = $16$ 位）：
long long（$8$ 字节 = $64$ 位）：
记忆方法：
- $n$ 位有符号整数范围是：
- $n$ 位无符号整数范围是：
常见整数类型与范围对照表
| 数据类型 | 字节数 | 位数 | 有符号范围 | 无符号范围 |
|---|---|---|---|---|
char |
$1$ B | $8$ | $-128 \sim 127$ | $0 \sim 255 $ |
short |
$2$ B | $16$ | $-32,768\sim 32,767 $ | $0\sim 65,535$ |
int |
$4$ B | $32$ | $-2,147,483,648\sim 2,147,483,647 $ | $0\sim 4,294,967,295 $ |
long long |
$8$ B | $64$ | $-9,223,372,036,854,775,808\sim 9,223,372,036,854,775,807$ | $0\sim 18,446,744,073,709,551,615$ |