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

Question

我想将两个最大位长度可能不同的大整数编码为一个整数。第一个整数是有符号的（可以是负数），而第二个是无符号的（总是非负数）。如果位长分别为m和n，则返回整数的位长应小于等于m + n.

只是 n（但不是 m）是预先知道的并且是固定的。该解决方案将作为示例用于组合 61+ 位的带符号 nanosecond timestamp 以及 256 位无符号随机性以形成带符号的 317+ 位唯一标识符。

我使用的是最新的 Python。在 special case when m == n.

中有一个相关的预先存在的问题解决了这个问题

Answer 1

此解决方案使用基本的位移位和位提取。使用位运算应该比使用更高级别的运算（例如求幂和乘法）更快。

基本解决方案与特殊情况非常相似，因为在任何一种情况下都只需要一个整数的最大位长度。但是，测试不是。

from typing import Tuple
import unittest


class IntMerger:
    """Reversibly encode two integers into a single integer.

    Only the first integer can be signed (possibly negative). The second
    integer must be unsigned (always non-negative).

    In the merged integer, the left bits are of the first input integer, and
    the right bits are of the second input integer.
    """
    # Ref: 
    def __init__(self, num_bits_int2: int):
        """
        :param num_bits_int2: Max bit length of second integer.
        """
        self._num_bits_int2: int = num_bits_int2
        self._max_int2: int = self._max_int(self._num_bits_int2)

    @staticmethod
    def _max_int(num_bits: int) -> int:
        return (1 << num_bits) - 1

    def merge(self, int1: int, int2: int) -> int:
        return (int1 << self._num_bits_int2) | int2

    def split(self, int12: int) -> Tuple[int, int]:
        int1 = int12 >> self._num_bits_int2
        int2 = int12 & self._max_int2
        return int1, int2


class TestIntMerger(unittest.TestCase):
    def test_intmerger(self):
        max_num_bits = 8
        for num_bits_int1 in range(max_num_bits + 1):
            for num_bits_int2 in range(max_num_bits + 1):
                expected_merged_max_num_bits = num_bits_int1 + num_bits_int2
                merger = IntMerger(num_bits_int2)
                maxint1 = (+1 << num_bits_int1) - 1
                minint1 = (-1 << num_bits_int1) + 1
                for int1 in range(minint1, maxint1 + 1):
                    for int2 in range(1 << num_bits_int2):
                        int12 = merger.merge(int1, int2)
                        # print(f'{int1} ({num_bits_int1}b), {int2} ({num_bits_int2}b) = {int12} ({int12.bit_length()}b)')
                        self.assertLessEqual(int12.bit_length(), expected_merged_max_num_bits)
                        self.assertEqual((int1, int2), merger.split(int12))
                self.assertEqual(int12.bit_length(), expected_merged_max_num_bits)


if __name__ == '__main__':
    unittest.main()

使用示例：

>>> merger = IntMerger(12)

>>> merger.merge(13, 8)
53256
>>> merger.split(_)
(13, 8)

>>> merger.merge(-13, 8)
-53240
>>> merger.split(_)
(-13, 8)

Answer 2

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

如果m和n没有固定，这个问题是不可能的，因为它要求我们编码两个（双位a, 一位b) and (一位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 3

如果您绝对必须具有完全可逆性，您需要至少放宽一个隐含的初始条件（因为如果您不单独记住任何这些数字和响应位长 R 小于 m+n，你只是不可挽回地失去了完全的可逆性）：

EITHER 你应该让 R 正好等于 m+n，在这种情况下，最简单的方法是 left-shift m-length 一个 n 位，然后添加 n-bit 数字（要反转，复制一份，right-shift n 位得到 m-length 一个，left-shift n 位和 subtract/bitwise-XOR from/with 编码数字得到n-length 一个),
或者您应该分别记住其中一个数字 somewhere/somehow（希望它对用户来说很常见？）和 bitwise-XOR 数字（要反转，只需 bit-wise XOR 结果存储的号码）；奖励积分，如果这对用户来说很常见，则每个用户在第一个之后的任何额外编码 ID 只会为存储需求增加 max(m,n) 位数据。

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

Reversibly encode two large integers of different bit lengths into one integer

python

integer

bit-manipulation

uniqueidentifier