进制系统与计算机存储

常见的进制

进制	基本符号
二进制	`0, 1`
八进制	`0, 1, 2, 3, 4, 5, 6, 7`
十进制	`0, 1, 2, 3, 4, 5, 6, 7, 8, 9`
十六进制	`0-9, A, B, C, D, E, F`

二进制：基数为2，符号集为{0,1}，权值为2的幂次。
八进制：基数为8，符号集为{0-7}，权值为8的幂次。
十六进制：基数为16，符号集为{0-9, A-F}，权值为16的幂次。
十进制：基数为10，符号集为{0-9}，权值为10的幂次。

进制转换方法

十进制转其他进制
- 方法：除以基数，倒序排列余数
- 适用：二进制(基数为2)、八进制(8)、十六进制(16)
其他进制转十进制
- 方法：按权展开求和。（如二进制 $ 101.11_{2} = 1 \times 2^{2} + 0 \times 2^{1} + 1×2^{0} + 1×2^{-1} + 1×2^{-2} $ ）
十进制小数转二进制
- 整数部分：除以2取余
- 小数部分：乘以2取整
二进制、八进制、十六进制互转
- 使用8421法进行快速转换

计算机存储单位

单位	大小关系	说明
位(bit)	最小单位	计算机处理的基本单元
字节	1字节 = 8位	基本存储单位

常见数据类型大小(通常情况)

类型	大小(bytes)	位数
int	4	32
float	4	32
double	8	64

原码、反码、补码

编码规则

原码：最高位为符号位(0正1负)，其余为数值位
反码：符号位不变，数值位取反
补码：反码+1（符号位不变）

4位二进制表示范围

编码类型	表示范围	说明
无符号	0 ~ 15 ($2^{4}-1$)	所有位表示数值
有符号原码	-7 ~ +7 ($-2^{3}-1$ ~ $2^{3}-1$)	最高位为符号位
有符号反码	-7 ~ +7 ($-2^{3}-1$ ~ $2^{3}-1$)	最高位为符号位
有符号补码	-8 ~ +7 ($-2^{3}$ ~ $2^{3}-1$)	补码能多表示一个负数

4位二进制编码表

二进制	无符号值	原码值	反码值	补码值
0000	0	+0	+0	0
0001	1	+1	+1	+1
0010	2	+2	+2	+2
0011	3	+3	+3	+3
0100	4	+4	+4	+4
0101	5	+5	+5	+5
0110	6	+6	+6	+6
0111	7	+7	+7	+7
1000	8	-0	-7	-8
1001	9	-1	-6	-7
1010	10	-2	-5	-6
1011	11	-3	-4	-5
1100	12	-4	-3	-4
1101	13	-5	-2	-3
1110	14	-6	-1	-2
1111	15	-7	-0	-1

注：补码中的1000(-8)是特殊表示，没有对应的原码和反码形式

不同的编码处理方法

计算方式	原码计算机	反码计算机
运算规则	比较绝对值，大数减小数	直接相加，循环进位修正
修正操作	无	最高位进位加到最低位
示例	(+5) + (-3) → 5-3=+2	00000101+11111100 → 00000010 (+2)

核心逻辑：

原码：符号位单独处理，数值部分按绝对值计算。
反码：允许符号位参与运算，但需处理循环进位。

浮点数存储：IEEE 754标准（32位单精度）

结构组成

部分	位数	说明
符号位	1位	`0`正数，`1`负数。
指数	8位	移码（Excess-127），实际指数 = E - 127。
尾数	23位	隐含最高位`1`（规格化数）或`0`（非规格化数）。

规格化数

条件：指数非全0/全1（$1 \le E \le 254$）。
公式：$(-1)^{S} × 1.M_{₂} × 2^{E-127}$。
范围：$\approx 1.175 \times 10^{-38}$ ~ $3.4×10^{38}$。

非规格化数

条件：指数全0（$E=0$）。
公式：$(-1)^S \times 0.M_{2} \times 2^{-126}$。
作用：填补接近零的数值间隙（最小正数$\approx 1.4×10^{-45}$）。

特殊值

±0：指数和尾数全0。
±∞：指数全1且尾数全0（如1.0/0.0）。
NaN：指数全1且尾数非0（如0/0）。

移码（Excess-127）逻辑

偏移目的：将指数范围从-126~+127映射为无符号数1~254，避免负数存储。
比较优势：直接对比存储值即可判断指数大小（如130 > 120对应实际指数3 > -7）。

位运算

核心位运算符表

运算符	名称	功能描述
`&`	按位与	两位同时为1则结果为1，否则为0
`\|`	按位或	两位有一个为1则结果为1，否则为0
`^`	按位异或	两位不同则结果为1，相同则结果为0
`~`	按位取反	单目运算符，将每一位取反 (1变0, 0变1)
`<<`	左移	将二进制位整体向左移动指定位数，低位补0，高位舍弃
`>>`	算术右移	将二进制位整体向右移动指定位数，高位补符号位(原最高位)，低位舍弃
`>>>`	逻辑右移	(Java, JS 等特有) 将二进制位整体向右移动指定位数，高位补0，低位舍弃

重要提示:

右移 (>>) 的行为：C/C++ 标准未明确规定对有符号数是逻辑右移还是算术右移，由编译器实现决定（绝大多数编译器对有符号数使用算术右移）。Java 和 JavaScript 明确区分 >> (算术右移) 和 >>> (逻辑右移)。

取反 (~) 的结果：结果取决于数据类型（有符号/无符号）和位数。对正整数 x，~x = -x - 1。

移位位数限制：左移/右移的位数 k 通常应小于数据类型的位数 n (如 k < 32 对于 int)。如果 k >= n，行为未定义 (C/C++) 或等价于 k % n (Java, Python)。

实用位运算技巧

以下技巧利用了位运算的独特性质，常用于算法优化、状态压缩和底层操作：

技巧	代码片段	说明
判断奇偶性	`(num & 1) == 0`	结果为 `true` 则为偶数 (最后一位是0)，`false` 为奇数 (最后一位是1)。
交换两个数 (无临时变量)	`a ^= b; b ^= a; a ^= b;`	利用异或性质 `a ^ b ^ b = a`。
取反加1 (求补码)	`~num + 1`	等价于 `-num` (对于整数)。
检查是否为 2 的幂	`(num & (num - 1)) == 0 && num > 0`	2的幂的二进制表示只有一个1。
计算整数绝对值 (32位 int)	`(num ^ (num >> 31)) - (num >> 31)`	利用算术右移得到符号位扩展。
获取最低位的 1	`lowbit = num & -num`	例如 `12 (1100) & -12 (0100) = 4 (0100)`。
统计 1 的个数 (Brian Kernighan 算法)	`while (num) { count++; num &= num - 1; }`	每次循环清除最低位的1，效率高。
模 2^k 运算	`num & ((1 << k) - 1)`	比 `num % (2^k)` 更快。
创建掩码 (mask)	`mask = (1 << k) - 1`	生成 `k` 个低位为 1 的掩码 (如 `k=4` -> `0b1111`)。
设置第 k 位为 1	`num \\|= (1 << k)`	将 `num` 的第 `k` 位 (0-based) 设为 1。
设置第 k 位为 0	`num &= ~(1 << k)`	将 `num` 的第 `k` 位 (0-based) 设为 0。
切换第 k 位 (翻转)	`num ^= (1 << k)`	将 `num` 的第 `k` 位 (0-based) 取反 (1变0, 0变1)。
检查第 k 位是否为 1	`(num & (1 << k)) != 0`	结果为 `true` 表示第 `k` 位是1。
提取连续的位域 (bitfield)	`(num >> start) & ((1 << length) - 1)`	从 `num` 的第 `start` 位开始提取 `length` 位。
异或加密/解密	`cipher = data ^ key; data = cipher ^ key;`	利用 `(data ^ key) ^ key = data` 性质实现简单加密。

使用位运算的注意事项:

可读性: 位运算有时会降低代码可读性，应酌情添加注释说明意图。
优先级: 位运算符优先级通常较低且易混淆，强烈建议多用括号明确运算顺序。
移植性: 涉及移位（尤其是有符号数右移）或取反结果依赖具体实现时需谨慎。
替代性: 现代编译器非常智能，很多时候 num * 2 会被优化为 num << 1，不必刻意追求位运算写法。优先考虑代码清晰度，在性能关键路径或特定算法（如状态压缩、位图）中再使用位运算。

编码类型	表示范围	说明
无符号	0 ~ 15 (\(2^{4}-1\))	所有位表示数值
有符号原码	-7 ~ +7 (\(-2^{3}-1\) ~ \(2^{3}-1\))	最高位为符号位
有符号反码	-7 ~ +7 (\(-2^{3}-1\) ~ \(2^{3}-1\))	最高位为符号位
有符号补码	-8 ~ +7 (\(-2^{3}\) ~ \(2^{3}-1\))	补码能多表示一个负数