如何将3个整数编码为2个整数？

Question

我有三个整数（x1，x2，x3）全部在[0,255]中。我需要将它们编码为两个整数（a和b），以便我可以确定性地将它们解码。约束是新整数的大小必须很小。 因此，我可以做a = 256*x1+x2，但这使得a比xi大得多。

有什么方法可以编码整数以使结果数保持很小？ 我没有定义什么是小，我想尽可能小。

一个类似的问题是将这些3数字编码为1。同样，新整数需要尽可能小。有什么办法吗？

Answer 1

欢迎来到信息理论 / PIGONHOLE原理。如果您想编码x不同的值，则需要有足够的位来区分x不同的事物。在您的情况下，有256 = 2 ** 8可能性（使用**用于指示），x1，x2 < /code>和x3。因此，总共有2 ** 24组合的可能性。因此，您需要2 ** 24组合。因此，24位。

可以使用范围0-4095中的12位数字来实现您的第一个编码。并且您的编码可以如下完成（其中％是剩余的操作，//是整数部门，因为它们在Python3中）：

a = (x1%16) * 256 + x2
b = (x1//16) * 256 + x3

使用：编码

x1 = (a//256) + (b//256) * 16
x2 = a%256
x3 = b%256

： 1数字再次需要2 ** 24可能性，因此数字需要在范围内0..16777215。这次编码是：

c = x1 + 256*x2 + 65536*x3

通过解码，

x1 = c%256
x2 = (c//256)%256
x3 = c//65536

您可以实现各种其他编码/解码。但是，它们的数字范围比这是无法实现的。