进制转换与位权

• 二进制小数的位权概念（2^-1、2^-2 …）
• 有限二进制小数对分母的约束条件
• 最简分数分母仅含 2 的因子即可有限表示

二进制小数的每一位代表 2^-n 的位权，因此一个数能被有限二进制精确表示，当且仅当它等于若干 2 的负幂之和。0.5 = 1 × 2^-1，正好是最高位的一位权，可以精确表示为 0.1。而 0.1 需要分解成 2^-1=0.5、2^-2=0.25、2^-3=0.125、2^-4=0.0625 等有限项的组合，但无论取多少位，剩余部分都无法完全消去，只能无限逼近，得到无限循环的二进制小数 0.0001100110011…。

判断依据是：一个数能写成有限二进制小数的充要条件是它化为最简分数后分母只含 2 的因子。0.5 = 1/2 分母只有 2，可以终止；0.1 = 1/10，分母含因子 5，无法用 2 的幂次表出，故只能无限循环。这正是浮点数无法精确表示 0.1 的根本原因。

• 十六进制位的位权（16 的幂）
• 位权与数字相乘求和
• 逐位展开求和的整体数值

0x2F3A 共 4 位，从低位到高位对应位权 16^0=1、16^1=16、16^2=256、16^3=4096。逐位展开：A=10 在个位贡献 10×1=10，3 在 16 位贡献 3×16=48，F=15 在 256 位贡献 15×256=3840，2 在 4096 位贡献 2×4096=8192。因此最高位 2 贡献的十进制值是 8192，整个数等于 10+48+3840+8192=12090。

十六进制是 16 的幂展开，每一位数字乘以对应 16^n 再求和即得十进制值。计算最高位时只需看该位所在位置 n，最高位 n=3，所以贡献是 2×16^3=8192。

• 乘 2 取整法转换小数
• 有限二进制表示的条件
• 最简分数分母为 2 的幂即有限表示

用乘 2 取整法：0.6875×2=1.375，取整 1，剩余 0.375；0.375×2=0.75，取整 0；0.75×2=1.5，取整 1，剩余 0.5；0.5×2=1.0，取整 1，剩余 0；结果从高位到低位依次为 1、0、1、1，即 0.6875 = 0.1011（二进制）。该数可以有限表示，因为 0.6875 = 11/16，化作最简分数后分母 16 = 2^4 只含因子 2，所以只需 4 位即可精确表示。

乘 2 取整法的本质是：每次乘以 2 把下一位二进制小数移到整数位，取整后继续。当小数部分变为 0 时终止，说明分母只含 2 的因子，可以有限表示。

• 整数部分按 2 的幂展开
• 小数部分按 2 的负幂展开
• 二进制小数位权与多项式求和

整数部分从高位到低位位权为 2^3、2^2、2^1、2^0，即 1×8 + 0×4 + 1×2 + 1×1 = 8+0+2+1 = 11。小数部分位权为 2^-1、2^-2、2^-3，即 1×0.5 + 0×0.25 + 1×0.125 = 0.5+0+0.125 = 0.625。两部分相加得 11.625。

小数点左移一位权变为原来的一半，右侧依次是 1/2、1/4、1/8。将整数与小数部分分别加权求和再合并，是进制转换的标准方法。

• 二进制最大位权定位
• 减法逐位构建二进制
• 逐位比较与借位定位

2^6=64 < 100 < 2^7=128，所以最高位是 2^6。步骤：100-64=36（对应 2^6 位，取 1）；36-32=4（对应 2^5 位，取 1）；4 小于 2^4=16、2^3=8、2^2=4，所以 2^4、2^3 位为 0，2^2 位取 1，4-4=0；2^1、2^0 位为 0。因此 100 = 1100100（二进制）。

减法法从大到小减去不超过剩余值的最高位权，被减掉的位取 1，跳过的位取 0。100 的二进制 1100100 对应 64+32+4，验证正确。

• 十进制转 8 位二进制
• 位反转操作
• 反转后按位权重新展开求值

217 = 128+64+16+8+1 = 11011001（二进制）。反转各位后得到 10011011。重新展开：1×2^7 + 0×2^6 + 0×2^5 + 1×2^4 + 1×2^3 + 0×2^2 + 1×2^1 + 1×2^0 = 128+0+0+16+8+0+2+1 = 155。

位反转是把最高位与最低位对调、次高与次低对调，其余类推。反转后原 11011001 变为 10011011，其十进制值通过位权重新计算为 155。

• 乘 2 取整法推导循环节
• 二进制有限表示与分母因子的关系
• 小数部分重复出现即判定循环节

用乘 2 取整：0.2×2=0.4 取 0，剩 0.4；0.4×2=0.8 取 0，剩 0.8；0.8×2=1.6 取 1，剩 0.6；0.6×2=1.2 取 1，剩 0.2；此时回到 0.2，进入循环。因此 0.2 = 0.001100110011…（二进制），循环节为 0011。原因在于 0.2 = 1/5，分母含因子 5，无法用 2 的幂次表示，故只能无限循环。而 0.5 = 1/2 分母只含因子 2，等于 0.1（二进制），有限表示。

乘 2 取整过程中，一旦小数部分回到某个已出现过的值，就说明开始了循环。0.2 在第 4 步回到 0.2，循环节为 0011。对比 0.5 在第一步即消去，说明分母决定是否可终止。

• 十进制与二进制、八进制、十六进制互转
• 八进制与二进制 3 位一组的关系
• 16 = 2^4，每 4 位一组转十六进制

173 = 128+32+8+4+1 = 10101101（二进制）。八进制按 3 位一组：010 101 101，对应 2 5 5，即八进制 255。十六进制按 4 位一组：1010 1101，对应 A D，即 0xAD。因为八进制一位正好对应 3 个二进制位，而二进制最低 3 位 101 = 5 就决定了八进制的末位是 5，更高位每 3 位一组继续对应。

8 = 2^3，所以二进制最低 3 位能确定八进制最低一位，从右往左每 3 位一组即可完成转换。同理 16 = 2^4，每 4 位一组。验证：255（八进制）= 2×64+5×8+5 = 128+40+5 = 173，正确。

• 2 的幂与 n 位全 1 的关系
• 十六进制位权
• 2^32 - 1 即 32 位全 1 的位权关系

2^32 是 1 后面跟 32 个 0，即 32 位二的最高位为 1 其余为 0。2^32 - 1 是 32 位全 1。32 位二进制每 4 位一组分成 8 组，每组都是 1111 = F，所以十六进制为 0xFFFFFFFF。每一位 F 对应十六进制位权：从低到高为 16^0、16^1、…、16^7，分别贡献 15×16^n。最高位 F 贡献 15×16^7 = 15×268435456 = 4026531840。

32 位全 1 二进制按 4 位分组，正好 8 个 F。每个 F 在位置 n 的贡献为 15×16^n。总和 = 16^8 - 1 = 2^32 - 1，验证公式正确。

• 补码的定义与表示范围
• 补码位模式的唯一性
• 补码 = 2^n - |x| 的负数计算

8 位补码表示范围是 [-128, 127]。计算 -128 的补码：其绝对值 128 的二进制是 10000000，但正数 128 超出 8 位补码范围。用公式：-128 = 2^8 - 128 = 256 - 128 = 128 = 10000000（二进制）。所以 -128 的 8 位补码是 10000000。该位模式唯一，因为补码对每个可表示的数与位模式一一对应，不存在原码、反码那样的正负 0 歧义。

补码 = 2^n - |x| 用于负数。对 -128，2^8 - 128 = 128，即 10000000。它是 8 位补码中唯一以 1 开头且数值为最小值的模式，且没有第二个数对应它，因此唯一。

• 八进制字面量位权
• 3 位权限位的含义
• 八进制每一位对应 3 个二进制权限位

0755 是八进制字面量（以 0 开头），三个数字 7、5、5 分别表示所有者、组、其他用户三类权限。每类权限用 3 个二进制位表示 r（读 4）、w（写 2）、x（执行 1）。7 = 111 = rwx，5 = 101 = r-x。因此 0755 对应所有者 rwx，组 r-x，其他 r-x，即 rwxr-xr-x。

八进制每一位恰好对应 3 个二进制权限位，因此 Unix 权限用八进制表示最直观。7=4+2+1 表示全部权限，5=4+1 表示读和执行但没有写权限。

• 点分十进制转二进制
• 网络序（大端）字节拼接
• 每字节独立转十六进制

每个十进制字节转二进制：192 = 11000000，168 = 10101000，10 = 00001010，5 = 00000101。拼接得到 32 位二进制：11000000 10101000 00001010 00000101。每字节转十六进制：192 = 0xC0，168 = 0xA8，10 = 0x0A，5 = 0x05，所以网络序为 4 字节 C0 A8 0A 05。

IPv4 地址本质上是一个 32 位无符号整数，网络序按大端存储，即最高有效字节在前。点分十进制中第一个数字对应最高字节，因此顺序就是 C0 A8 0A 05。

• 整数转换的除基取余法
• 小数转换的乘基取整法与 3/4 位分组法
• 2 的幂进制间按位分组直接转换

整数转换用除基取余法：不断除以目标进制并记录余数，最后逆序排列。由于 8=2^3、16=2^4，二进制与八进制、十六进制之间可以按 3 位或 4 位一组直接转换，无需十进制作为中间态。小数转换用乘基取整法：不断乘以目标进制取整数部分，正序排列。二进制小数转八进制按 3 位一组、转十六进制按 4 位一组，不足位补 0。

2 的幂进制之间可以直接按位分组，效率最高。十进制与其它进制互转才需要除基取余或乘基取整。掌握算法的统一性（按权重逐位展开）即可应对各类转换。

• 二进制小数多项式展开
• 位权有限性与分母因子
• 有限位权只能组合出分母为 2 的幂的数

二进制小数可以写成多项式和 D = Σ di × 2^-i，其中 di 是 0 或 1。每一项都是 2 的负幂，因此任意有限二进制小数等于形如 n/2^k 的数，即分母只含因子 2 的最简分数。而 0.1 = 1/10，最简分数分母 10 含因子 5，无法写成 n/2^k，因此有限位二进制多项式无法精确表示 0.1，只能无限逼近。

这是利用位权多项式展开的数学本质：有限位权只能组合出二进制的分母。0.1 的分母含 5，与 2 互质，故不可能在有限位内精确表示。这正是浮点误差的根源。

• 短除法（除基取余）步骤
• 余数逆序排列的含义
• 余数严格小于基保证位数字合法

转八进制：12345÷8=1543 余 1；1543÷8=192 余 7；192÷8=24 余 0；24÷8=3 余 0；3÷8=0 余 3。逆序排列余数得 30071（八进制）。转十六进制：12345÷16=771 余 9；771÷16=48 余 3；48÷16=3 余 0；3÷16=0 余 3。逆序得 0x3039（十六进制）。验证：3×4096+0×256+3×16+9 = 12288+0+48+9 = 12345，正确。

除基取余得到的余数是当前最低位，商继续迭代，因此最后得到的余数要逆序排列才是最高位到最低位。每一步的余数都严格小于基，保证位数字合法。

• 16 = 2^4 的位权关系
• 4 位一分组转换
• 最高位不足 4 位时补 0 处理

因为 16 = 2^4，一个十六进制位正好对应 4 个二进制位，所以从右往左每 4 位一组即可直接转换，无需计算十进制。对 0b101111001101：从右往左分组，1011 1100 1101。每组转十六进制：1011 = B，1100 = C，1101 = D，所以结果为 0xBCD。

4 位二进制最大是 1111 = 15，正好覆盖十六进制 0-F，所以分组绝对无损。分组时若最高位不足 4 位需补 0。反向转换时每个十六进制位展开为 4 位二进制即可。

• 有限进制小数与分母因子的关系
• 进制基数与分母约分
• 有限 N 进制小数等于 m/N^k 的约分形式

一个有理数 p/q 在 N 进制下能有限表示，当且仅当在约分为最简分数后，q 的所有质因数都能整除 N。因为有限 N 进制小数等于若干 N 的负幂之和，即形如 m/N^k 的数，其分母只能是 N^k 的约数，质因数来自 N。若 q 含 N 没有的质因数，则无法约分掉，只能无限循环。例如 0.1 = 1/10 在二进制（N=2）下分母含 5，而 5 不整除 2，故无法终止。

这是进制转换的一般性定理。能终止等价于分母能化为 N 的幂，等价于分母的质因数都整除 N。反过来若分母含与 N 互质的质因数，则必然无限循环。

• 补码表示负数
• 无符号解读同一位模式
• 最高位位权在补码为负、无符号为正

在补码表示中，负数以最高位为符号位，例如 8 位 -1 的补码是 11111111。若把同一模式 11111111 当作无符号数解读，则得到 255（十进制）、0xFF（十六进制）。因此同一串二进制在不同解读下数值完全不同，取决于是否把最高位贡献的权重视为 -2^7（补码）还是 +2^7（无符号）。

补码中最高位权重是负的，无符号中最高位权重是正的。所以 -1 补码 11111111 与无符号 255 共享同一位模式，这正是 C 语言中 int 与 unsigned 强制转换时数字可能骤变的原因。

• 62 进制转换
• 字符数压缩比估算
• 位数与进制大小的对数关系

用除基取余法：123456789÷62=1991238 余 33；1991238÷62=32116 余 46；32116÷62=518 余 0；518÷62=8 余 22；8÷62=0 余 8。字符表 0-9 对应 0-9，a-z 对应 10-35，A-Z 对应 36-61。余数 8→'8'，22→'m'，0→'0'，46→'K'，33→'x'，逆序得 "8m0Kx"。十进制 123456789 有 9 位，62 进制表示约 5 位，节省约 4 位字符（约 44% 缩短）。

因为 62^5 ≈ 916,132,832 > 123,456,789，而 62^4 ≈ 14,776,336 < 123,456,789，所以 62 进制只需 5 位。位数越大的进制，同样数值所需字符越少，这就是短链接压缩的原理。