进制转换 + 编码 + 位运算

PART1：进制转换（优先以二进制为桥梁）

一、十进制转非十进制（通用所有进制）

1. 整数部分：除基取余法

方法：反复除以目标进制基数，直到商为0，逆序取所有余数
例子：

• 十进制 13 转二进制
  13÷2=6余1 → 6÷2=3余0 → 3÷2=1余1 → 1÷2=0余1
  逆序取余：1101
• 十进制 255 转十六进制
  255÷16=15余15 → 15÷16=0余15（15对应F）
  逆序取余：FF

2. 小数部分：乘基取整法

方法：反复乘以目标进制基数，顺序取每次乘积的整数部分，直到小数为0或达到精度
例子：

• 十进制 0.625 转二进制
  0.625×2=1.25（取1）→ 0.25×2=0.5（取0）→ 0.5×2=1.0（取1）
  顺序取整：0.101
• 十进制 0.75 转八进制
  0.75×8=6.0（取6）
  顺序取整：0.6
• 注意到这个转换过程有可能永远算不到小数为0，一般题目会给比较特殊的数字，或者限定算出几位小数就行
• 所以也有个知识点，0.9-0.8==0.1 判断是false，因为小数无法精准转二进制存储，也就无法精准判断相等

二、非十进制转十进制（位权法，通用所有进制）

核心原理：每个数位上的数字 × 对应位权，所有结果相加
假设原始数字为p进制数：

• 个位数 p⁰‌ + 十位数 p¹‌ + 百位数* p‌²‌…… +
• 小数部分则依次乘p的-1、-2、-3次方并求和

注意到任意数字的0次方都是1，所以个位数总是乘1，十位数乘p的1次方即乘p，下一位乘p p，再下一位乘p p * p……
小数部分对应到1/p， 1/p/p， 1/p/p……（这样就不用考虑负数幂）
例子：

1. 二进制 1101.101 转十进制
   整数：1×2³ + 1×2² + 0×2¹ + 1×2⁰ = 8+4+0+1=13
   小数：1×2⁻¹ + 0×2⁻² + 1×2⁻³ = 0.5+0+0.125=0.625（2⁻¹即1/2，2⁻²即1/2/2，2⁻³即1/2/2/2……）
   结果：13.625
2. 十六进制 A3.5 转十进制
   整数：10×16¹ + 3×16⁰ = 160+3=163
   小数：5×16⁻¹ = 0.3125（16⁻¹即1/16）
   结果：163.3125
3. 八进制 35.6 转十进制
   整数：3×8¹ +5×8⁰=24+5=29
   小数：6×8⁻¹=0.75（8⁻¹即1/8）
   结果：29.75

三、占位法快速转二进制（⭐⭐⭐⭐⭐）

原理：
根据上述非十进制转十进制，我们发现所有数都能写成一堆2的幂的和。
例如0b1101 = 1 8 + 1 4 + 0 2+ 1 1= 8 + 4 + 0 + 1 = 13，加该幂则对应二进制位为1，否则为0，所以只需要把待转换十进制数拆成一堆2的幂的和，就能知道对应二进制。
注意从大到小去拆
示例： 37先拆出32，剩下的5可以拆出4+1，而16、8、2没用上，对32、16、8、4、2、1，用写1，不用写0，即100101。按二进制转十进制的规则，正好是1+4+32，恢复37。
常用2的幂（必背）：2⁰=1, 2¹=2, 2²=4, 2³=8, 2⁴=16, 2⁵=32, 2⁶=64, 2⁷=128

例子：

• 十进制 13 = 8+4+1 → 二进制 1101
• 十进制 42 = 32+8+2 → 二进制 101010

四、2/8/16进制互相转换（以二进制作为桥梁，不要用十进制）

速算核心：利用占位法记住15以内所有数的二进制

1. 二进制 ↔ 八进制（3个二进制位合1个八进制位/1个八进制位拆3个二进制位）

规则：整数从右往左、小数从左往右，每3位一组，不足补0；每组对应1位八进制（0-7）
例子：

• 二进制转八进制：1101101 → 分组 1，101，101 → 补0 001，101，101 → 八进制 155
• 八进制转二进制：37.4 → 拆分 011 111 . 100 → 二进制 11111.1

2. 二进制 ↔ 十六进制（4个二进制位合1个十六进制位/1个十六进制位拆4个二进制位）

规则：整数从右往左、小数从左往右，每4位一组，不足补0；每组对应1位十六进制（0-9,A-F）
例子：

• 二进制转十六进制：11011010 → 分组 1101 1010 → 十六进制 DA
• 十六进制转二进制：A3.5 → 拆分 1010 0011 . 0101 → 二进制 10100011.0101

编码

• 关于编码类问题取几位二进制，只要能覆盖你的数字和符号位就行，一般是8位，7以内的数4位也行。

  一、基本概念

• 机器数：计算机中存储的带符号二进制数，最高位为符号位（0=正，1=负）
• 真值：机器数对应的实际十进制数值（如机器数10000001原码的真值是-1）

二、原码

1. 定义与计算

• 正数：符号位为0，其余位为数值的绝对值
• 负数：符号位为1，其余位为数值的绝对值
• 示例：+5（8位）原码=00000101；-5（8位）原码=10000101

2. 表示范围

• 8位原码：11111111 ~ 01111111即-127 ~ +127
• 16位原码：-32767 ~ +32767

3. 缺点

• 加减法运算复杂（减法不能直接转加法）
• 零有两种表示：+0=00000000，-0=10000000

三、反码

1. 定义与计算

• 正数：反码 = 原码
• 负数：符号位不变，其余位按位取反
• 示例：-5（8位）反码=11111010

2. 运算规则

• 符号位参与运算，若最高位有进位，则将该进位加到最低位（循环进位）

• 示例：用反码计算 2 + (-1)

  • 2反码=00000010，-1反码=11111110
  • 相加：00000010 + 11111110 = 100000000（最高位有进位1）
  • 循环进位：00000000 + 1 = 00000001（结果正确，为1）

3. 核心问题

• 零仍有两种表示：+0=00000000，-0=11111111
• 循环进位增加了硬件电路复杂度

四、补码

1. 定义与计算

• 正数：补码 = 原码 = 反码
• 负数：补码 = 反码 + 1

• 快速计算技巧：将正数原码从右往左扫描，遇到第一个1后，左边所有位取反，符号位变1

  • 示例：-5原码=00000101 → 第一个1在第0位 → 左边取反+符号位1 → 11111011（补码）

2. 补码转真值

• 正数：直接转十进制
• 负数：补码先-1得反码，再取反得原码，再转十进制（注意取反时符号位不变）

• 示例：

  • 补码10111011 → -1得10111010 → 取反得11000101 → 真值-69

3. 表示范围

• 8位补码：-128 ~ +127（原码的-0=10000000被用来表示-128）
• 16位补码：-32768 ~ +32767
• 特点：无-0，用原码的-0表示最小负数-128

4. 核心优势

• 无需循环进位，符号位自然参与运算，结果直接正确
• 解决了零的二义性问题，硬件实现最简单（只需加法器）
• 反码可以直接进行加减法运算，规则是：符号位参与运算，若最高位有进位，则将该进位加到最低位（循环进位）
• 补码在反码基础上加1，巧妙解决了-0的问题（原码的-0=10000000被用来表示-128）

• 补码运算无需循环进位，符号位自然参与运算，结果直接正确，硬件实现更简单
  例子：6+(-4) → 0000 0110 + 1111 1100 → 0000 0010 即2（高位溢出丢弃）

  五、高频考点&易错点

• 有符号数→无符号数转换

  • 直接将补码当作无符号数解析
  • 32位int a=-5 → unsigned int b=a=4294967291（-5还是做补码存储，但取出时连带符号位都计算成数值位，一般不用真算，记着无符号小负数会得到一个很大的正数就行）

4. 补码溢出判断

   • 加法运算中，最高位和次高位进位不同 → 发生溢出（我们常说的爆int了）

5. 其他考点

   • ✅ 补码可以将减法转加法，简化硬件设计
   • ❌ 任意整数的反码和补码都差1位（正数原反补码均相同）
   • ❌ 原码计算1+(-1)=0（注意是原码计算，0001+1001=1010即-2）
   • ✅ 反码计算加减法结果都正确，但解决不了-0问题

速记：正数原反补码一样，负数原码取反+1得补码，负数补码-1取反恢复原码，符号位不参与取反
_

位运算

一、6个基础位运算符（都是二进制对位比较运算，无进位借位）

• 这些运算符都可以在代码里用，像代码中^代表异或，不是数学里的幂

• ~取反运算时符号位也取反，注意和反码的取反区分，反码取反不包括符号位

  二、复合赋值位运算符

• a &= b 等价于 a = a & b
• a |= b 等价于 a = a | b
• a ^= b 等价于 a = a ^ b
• a <<= n 等价于 a = a << n
• a >>= n 等价于 a = a >> n

三、必考高频考点

1. 异或交换两个变量（无需临时变量）

• 核心公式：a=a^b; b=a^b; a=a^b;

2. 位运算常用技巧

• 二进制位&0能把该位变0，&1则结果不变，1&1还是1，0&1还是0。
• 二进制位|1能把该位变1，|0则结果不变，0|0还是0，1|0还是1.
• <<1相当于乘2，<<2相当于乘4，<<3相当于乘8……
• >>1相当于/2，>>2相当于/4，>>3相当于/8……
• 异或运算特性：a ^ a=0、a ^ 0=a、若a ^ b=c，则a ^ c=b，b ^ c=a

3. 移位运算考点

• 正数：x << n = x × 2ⁿ，x >> n = x ÷ 2ⁿ（向下取整）
• 负数：算术右移补符号位，结果还是向下取整，相当于绝对值向上取整（如-5 >> 1 = -3）
  这里还是向上取整，注意 -2.5的下是-3，不是-2。
• 易错：左移n再右移n不一定能还原（考虑数值位左移溢出）

4. 优先级问题

• 位运算优先级 低于 关系运算符（==、!=、<、>）
• 易错：5 & 3 == 1 等价于 5 & (3 == 1) = 0

四、高频易错点

1. ✅ 位运算只能用于整数类型，浮点数不能进行移位运算
2. ✅ ~0 的结果是 -1（00000000 -> 11111111(补码) -> 11111110(反码) -> 100000001(原码) 即-1）
3. ✅ 有符号数右移是算术右移，补符号位；无符号数右移是逻辑右移，补0
4. ❌ a << 2 >> 2 一定等于a（溢出情况不成立）
5. ❌ (a | 3) == 3 说明a的二进制除了低2位都是0，a有可能是0、1、2、3
6. ✅ (a & 3 & 1) == 0 等价于 (a & 1) == 0，可判断偶数（&3是看后两位是不是1，&1是看最后一位是不是1）
7. ❌ 010 << 1 = 0100(010是八进制8，8 << 1 = 16，0100是八进制数64)

五、典型计算

1. a&b|(c^d)，a=3,b=7,c=15,d=4

   • 计算：3(0011)&7(0111)=3(0011)，15(1111)^4(0100)=11(1011)，3(0011)|11(1011)=11(1011)

2. unsigned char c=0x0F; c=c<<3;

   • 计算：0x0F=15，15 2 2 * 2 = 120

3. 补码11111101>>1

   • 算术右移补1，得11111110，十进制-2，也可以转十进制再除以2：11111101(补)=11111100(反)=100000011(原)，即-3，-3>>1得-2(除以2向下取整)