如何将3个[0,255]区间整数可逆编码为2个或1个尽可能小的整数

• 编码为2个整数时，理论上两个整数的最小可能最大取值为4095，不存在两个整数最大值小于4095的无损编码方案
• 编码为1个整数时，理论上编码后整数的最小可能最大取值为16777215，不存在更小上界的无损编码方案

原理说明 #

3个取值在[0,255]的整数总共有256*256*256 = 16777216种不同组合。如果编码为两个整数a、b，要让两个数的取值尽可能小（即最坏情况下的数值最小），需要让两个数的可承载组合数尽可能均匀，乘积刚好覆盖总组合数：4096 * 4096 = 16777216，刚好匹配总组合数，此时a、b的取值范围均为[0,4095]，达到理论下界。

编码逻辑 #

1. 先把三个8位整数拼接为一个24位的中间值：
   mid = (x1 << 16) | (x2 << 8) | x3
2. 把24位中间值拆分为两个12位的整数：
   a = mid >> 12 // 取高12位
   b = mid & 0xfff // 取低12位

解码逻辑 #

1. 用a、b还原24位中间值：
   mid = (a << 12) | b
2. 从中间值拆分出三个原始整数：
   x1 = (mid >> 16) & 0xff
x2 = (mid >> 8) & 0xff
x3 = mid & 0xff

注：题面提到的a=256*x1 +x2、b=x3方案不是最优，该方案中a的最大取值为65535，远大于4095的理论下界。

原理说明 #

单整数编码需要覆盖全部16777216种组合，因此编码后整数的取值范围最小为[0, 16777215]，不存在上界更小的无损编码。

编码逻辑 #

直接将三个8位整数拼接为24位整数即可：
res = (x1 << 16) | (x2 << 8) | x3

解码逻辑 #

从24位整数中按位拆分出三个原始值：
x1 = (res >> 16) & 0xff
x2 = (res >> 8) & 0xff
x3 = res & 0xff

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