1.2 位与信息存储01 用位来表示信息二进制的由来莱布尼茨Leibniz, 1703 年发明了现代二进制计数体系受到中国古代《周易》八卦的启发阴爻⚋→ 0阳爻⚊→ 1八卦的三爻排列对应 3 位二进制编码☰111, ☱110, ☲101, ☳100, ☴011, ☵010, ☶001, ☷000为什么使用二进制1. 电子电路天然适配最简单的电子元件只需区分两种状态高电平/低电平通/断用两个终端设备输入/输出各两态即可实现基础的二进制逻辑2. 抗干扰性强二值信号对噪声的容忍度远高于多值信号模拟信号中引入噪声后波形变形严重二值数字信号即使受噪声影响只要仍能区分高低电平信息就不会丢失3. 与布尔代数完美对应布尔代数George Boole, 1854 年创立本身就是二值逻辑体系二进制运算 布尔运算 数字电路的基本操作进制系统进制基数BaseC 语言前缀示例二进制Binary20b0b1010八进制Octal800177十进制Decimal10无255十六进制Hexadecimal160x0xFF十六进制数字0 1 2 3 4 5 6 7 8 9 A B C D E FA10, B11, …, F15进制转换R 进制 → 十进制底 - 权展开法D∑idi×RiD \sum_{i} d_i \times R^iDi∑​di​×Ri每一位的数字 × 该位的权值R位置R^{\text{位置}}R位置然后求和示例(1011)21×230×221×211×2082111(1011)_2 1 \times 2^3 0 \times 2^2 1 \times 2^1 1 \times 2^0 8 2 1 11(1011)2​1×230×221×211×2082111十进制 → R 进制短除法整数部分不断除以 R记录余数余数从下往上读先得到的余数是低位小数部分不断乘以 R取整数部分从上往下读十进制 → 二进制2 的幂分解法将十进制数分解为若干个 2 的幂之和5332164125242220(110101)253 32 16 4 1 2^5 2^4 2^2 2^0 (110101)_25332164125242220(110101)2​二进制 ↔ 十六进制4 位分组法⭐每4 位二进制 1 位十六进制因为24162^4 162416二进制 → 十六进制从右向左每 4 位一组高位不足补 0十六进制 → 二进制每位十六进制展开为 4 位二进制二进制 0011 1010 1001 0101 十六进制 3 A 9 5 → 0x3A951 Byte 8 bit 2 位十六进制数二进制 ↔ 八进制3 位分组法每3 位二进制 1 位八进制因为2382^3 8238LSB 与 MSBLSBLeast Significant Bit最低有效位即二进制数的最右一位MSBMost Significant Bit最高有效位即二进制数的最左一位C 语言数据类型大小不同平台上 C 语言基本数据类型占用字节数数据类型Typical 32-bitIA32x86-64char111short222int444long448long long8不适用8float444double888long double因平台而异10/1210/16char *指针448关键差异在 x86-64 上long和指针从 4 字节扩展到 8 字节02 位级操作布尔代数Boolean Algebra乔治·布尔George Boole于 1854 年创立了布尔代数它是数字电路与位运算的数学基础。四种基本运算及真值表ABA AND B与A OR B或NOT A非A XOR B异或000010010111100101111100异或XOR的理解相同为 0不同为 1——可看作 不进位加法 位向量运算将布尔运算扩展到位向量bit vector即对每一位独立执行相同的布尔运算0110 1001 0110 1001 0110 1001 0101 0101 | 0101 0101 ^ 0101 0101 ~ 0110 1001 ----------- ----------- ----------- ----------- 0100 0001 0111 1101 0011 1100 1001 0110对应十六进制运算表达式结果AND与0x69 0x550x41OR或0x69 | 0x550x7DXOR异或0x69 ^ 0x550x3CNOT非~0x690x96运算步骤十六进制 → 二进制 → 逐位运算 → 二进制 → 十六进制位向量的集合表示位向量可用来表示有限集合中的子集——第iii位为 1 表示元素iii属于该集合位向量01101001→ 集合A{0,3,5,6}A \{0, 3, 5, 6\}A{0,3,5,6}位向量01010101→ 集合B{0,2,4,6}B \{0, 2, 4, 6\}B{0,2,4,6}位运算集合运算结果A B交集01000001→{0,6}\{0, 6\}{0,6}A | B并集01111101→{0,2,3,4,5,6}\{0, 2, 3, 4, 5, 6\}{0,2,3,4,5,6}A ^ B对称差00111100→{2,3,4,5}\{2, 3, 4, 5\}{2,3,4,5}~A补集10010110→{1,2,4,7}\{1, 2, 4, 7\}{1,2,4,7}C 语言中的位运算符C 语言提供 4 种按位运算符操作对象为整型数据的每一个二进制位运算符名称说明按位与两位都为 1 则为 1|按位或至少一位为 1 则为 1^按位异或两位不同则为 1~按位取反0 变 11 变 0逻辑运算符 vs 位运算符 ⚠️C 语言的逻辑运算符,||,!与位运算符,|,~容易混淆特性逻辑运算符||!位运算符|~^操作对象将整个值视为 真 非零或 假 零对每一个二进制位独立运算返回值0假或 1真按位运算后的整数结果短路求值✅ 支持❌ 不支持示例对比// 逻辑运算!0x41→0x00// 非零值取逻辑非 假!0x00→0x01// 零值取逻辑非 真0x690x55→0x01// 两个非零值逻辑与 真0x69||0x55→0x01// 至少一个非零逻辑或 真// 位运算~0x41→0xBE// 按位取反0x690x55→0x41// 按位与移位运算Shift Operations左移Left Shift所有位向左移动kkk位右边补 0等价于乘以2k2^k2k不溢出时右移Right Shift右移分两种情况类型适用对象补位规则效果逻辑右移无符号数左边补0无符号除以2k2^k2k算术右移有符号数左边补符号位MSB有符号除以2k2^k2k向下取整移位运算示例8 位操作数二进制操作逻辑结果算术结果1100 0011 20011 00001111 00000110 0101 20001 10010001 10011100 0011 20000 11000000 1100⚠️未定义行为当移位量k0k 0k0或k≥k \geqk≥字长位宽时C 语言标准规定行为未定义。实际中大多数机器取kmod wk \mod wkmodwwww为字长但不应依赖此行为。扩展话题量子计算经典计算机使用比特bit状态只能是 0 或 1量子计算机使用量子比特qubit可以同时处于 0 和 1 的叠加态我国 “九章二号” 光量子计算原型机已在特定任务上展现出量子优越性量子计算并非取代经典计算而是在某些特定问题如大数分解、搜索上具有指数级加速的潜力03 内存、指针与字符串字节寻址的内存模型内存在概念上是一个巨大的字节数组每个字节有一个唯一的地址这种组织方式称为字节寻址Byte-addressable地址空间的计算若地址位数为mmm每个地址存放nnn位数据则总的可寻址空间为2m×n2^m \times n2m×n位实际系统中n8n 8n81 字节因此32 位地址空间2322^{32}232字节 4 GB64 位地址空间2642^{64}264字节 ≈1.8×10191.8 \times 10^{19}1.8×1019字节极大常用容量单位符号含义大小KKilo千2102^{10}210 1,024MMega兆2202^{20}220≈ 100 万GGiga吉2302^{30}230≈ 10 亿TTera太2402^{40}240字Word与字长字长Word SizeCPU 一次处理数据的位数决定了虚拟地址空间大小对于www位字长的机器虚拟地址范围为0∼2w−10 \sim 2^w - 10∼2w−1不同字长下的地址间距类型32 位系统64 位系统字节间距1 字节1 字节字间距4 字节8 字节在 32 位系统中相邻 字 地址相差 4如 0x00, 0x04, 0x08在 64 位系统中相邻 字 地址相差 8如 0x00, 0x08, 0x10。字节序Byte Ordering⭐ 重点多字节数据在内存中的存储顺序有两种约定大端法Big Endian最高有效字节MSB存放在最低地址符合人类阅读习惯高位在前代表Sun SPARC、网络协议 网络字节序 小端法Little Endian最低有效字节LSB存放在最低地址代表Intel x86、x86-64、ARM现代主流示例存储int类型变量值为0x01234567起始地址0x100大端法Big Endian 地址 0x100 0x101 0x102 0x103 内容 01 23 45 67 ← 高位在低地址 小端法Little Endian 地址 0x100 0x101 0x102 0x103 内容 67 45 23 01 ← 低位在低地址记忆口诀小端 小低位字节放小低地址跨平台实测数据课件原始示例以变量值0x01234567在不同平台的内存布局平台类型字节序内存内容低地址→高地址Linux 32 (IA32)int小端67 45 23 01Linux 64 (x86-64)int小端67 45 23 01Sun (SPARC)int大端01 23 45 67Linux 64 (x86-64)long int(8B)小端67 45 23 01 00 00 00 00Sun (SPARC)long int(8B)大端00 00 00 00 01 23 45 67long int在 x86-64 上为 8 字节高 4 字节补零指针Pointer的表示指针的值是其所指向对象的内存地址指针本身也是数据占用空间 机器字长不同平台上指针的值指向同一个int变量平台指针大小存储内容小端/大端说明Linux 32 (IA32)4 字节28 F5 FF BF栈地址小端存储Linux 64 (x86-64)8 字节78 FD FF FF FF 7F 00 00更大的地址空间Sun (SPARC)4 字节EF FF FA 0C大端存储不同机器/操作系统/编译器可能为同一变量分配不同的地址字符串String的表示C 语言字符串 以 null 字符\0即0x00结尾的字符数组每个字符使用 ASCII 编码占 1 字节字符串12345在内存中的存储字节 31 32 33 34 35 00 字符 1 2 3 4 5 \0重要特性字符串的存储与字节序无关因为字符串是按字节逐一存储的不存在 多字节数据的高低位 问题。无论大端还是小端系统字符串的内存布局完全相同。本节小结本节涵盖了信息在计算机中的位级表示与操作的核心内容二进制基础从莱布尼茨与八卦的历史渊源到二进制被采用的三大原因硬件适配、抗干扰、布尔代数对应进制系统与转换掌握底 - 权展开法、短除法、4 位分组法等关键转换方法数据类型大小理解不同平台32 位 vs 64 位上数据类型占用空间的差异布尔代数与位运算四种基本运算AND/OR/NOT/XOR、位向量的集合表示、C 语言位运算符逻辑运算与位运算的区别逻辑运算符看整体真假位运算符逐位操作——这是常见考点移位运算左移补零右移分逻辑右移补零和算术右移补符号位内存模型字节寻址、地址空间、字与字长的概念字节序大端法高位在低地址vs 小端法低位在低地址及跨平台的实际差异指针与字符串指针存储地址且大小等于字长字符串逐字节存储与字节序无关