算术编码：如何高效利用64位字中的剩余容量？

首先明确核心数据：单个26字母字符的熵是log2(26)≈4.7004位，64位理论上可容纳64/4.7004≈13.616个字符，你的13.5个目标完全在理论可行范围内。下面是一种简洁高效的实现思路：

最优块打包方案：2个64位字装27个字符 #

直接计算可知：

• 27个字符的26进制总位数：27 * log2(26)≈126.91位
• 2个64位字的总容量是128位，剩余约1.09位空间，完全足够容纳27个字符的编码结果

平均下来就是27/2=13.5个字符/64位，刚好达成你的目标。

编码流程 #

1. 将27个字符（每个映射为0-25的整数）转换为一个大整数：
   num = c0 + c1*26 + c2*26² + ... + c26*26^26
2. 将这个127位左右的大整数拆分为两个64位字：
   • 低64位：num & 0xFFFFFFFFFFFFFFFF
   • 高64位：num >> 64（由于总位数不足128，高64位的最高几位会是0，不影响存储）

解码流程 #

1. 将两个64位字拼接为一个大整数（以128位整数为例）：
   num = (uint128_t)high_word << 64 | low_word
2. 循环对num取模26得到字符值，再将num除以26，直到取出27个字符：

   chars = []
   for _ in range(27):
       chars.append(num % 26)
       num = num // 26
   chars = chars[::-1]  # 恢复原顺序
   

方案优势 #

• 空间利用率拉满：几乎完全耗尽128位的可用空间，刚好达到13.5个字符的平均密度
• 实现简洁：仅依赖大整数运算，现代编程语言（C/C++的uint128_t、Python原生int、Go的big.Int）都能轻松实现，无需复杂的状态跟踪或编码表
• 性能损耗低：编码解码都是线性操作，比可变长度编码或逐位拼接的效率高很多

备选方案（无128位整数支持时） #

如果环境不支持128位整数，可以将27个字符的编码拆分为3个32位字，或者用数组模拟大整数的乘26加字符、除26取余操作，但会增加少量代码复杂度，不过逻辑依然清晰。

内容的提问来源于stack exchange，提问作者Dov