将两个不同位长的大整数可逆地编码为一个整数

Question

我想将两个最大位长可能不同的大整数编码为一个整数。第一个整数是有符号的（可以是负数），而第二个是无符号的（总是非负数）。如果位长分别为m和n，则返回整数的位长应小于或等于m + n。只是n（但不是m）是预先知道的并且是固定的。作为示例，该解决方案将用于将61 位以上的有符号纳秒时间戳与 256 位无符号随机性结合起来，以形成一个有符号 317 位以上的唯一标识符。我正在使用最新的 Python。有一个相关的预先存在的问题，它在特殊情况下m == n解决了这个问题。

Answer 1

由于n是固定的，所以问题很简单：将 ( a , b )编码为a •2 ⁿ + b。

如果m和n不固定，则问题是不可能的，因为它要求我们将（两位a，一位b）和（一位a，两位b）都编码为三位，这意味着我们必须编码十二种可能性 (0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3) ), (2, 0), (2, 1), (3, 0), (3, 1) 三种比特的八种组合，这是不可能的。

Answer 2

如果您绝对必须具有完全可逆性，则需要放宽至少一个隐含的初始条件（因为如果您不单独记住这些数字中的任何一个并且响应位长 R 小于 m+n，则您将不可撤销地失去完全可逆性)：

• 要么你应该让 R 完全等于 m+n，在这种情况下，最简单的方法是将 m 长度左移 n 位，然后添加 n 位数字（反转，复制，右移由 n 位得到 m 长度的 1，左移 n 位并从/与编码数减去/按位异或得到 n 长度的数），

• 或者你应该在某处/以某种方式单独记住其中一个数字（希望它对用户来说很常见？）并且只是按位异或数字（反转，只是按位异或结果与存储的数字）；奖励积分，如果这对用户来说很常见，那么每个用户超过第一个的任何额外编码 ID 只会增加 max(m,n) 位数据到存储需求。