将具有不同位长的两个大整数可逆编码为一个整数 [英] Reversibly encode two large integers of different bit lengths into one integer

问题描述

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

I want to encode two large integers of possibly different maximum bit lengths into a single integer. The first integer is signed (can be negative) whereas the second is unsigned (always non-negative). If the bit lengths are m and n respectively, the bit length of the returned integer should be less than or equal to m + n.

仅n(但不是m)是预先已知的并且已修复.作为解决方案的示例，将结合使用已签名的纳秒时间戳 61+位和256位无符号随机性组成一个有符号的317+位唯一标识符.

Just n (but not m) is known in advance and is fixed. The solution will as an example be used to combine a signed nanosecond timestamp of 61+ bits along with 256 bits of unsigned randomness to form a signed 317+ bit unique identifier.

我正在使用最新的Python.在特殊情况下，当m == n 时，存在一个相关的先前问题可以解决此问题.

I'm using the latest Python. There is a related preexisting question which addresses this in the special case when m == n.

推荐答案

此解决方案使用基本的位移位和位提取.使用位运算应比使用幂运算和乘运算等更高级别的运算更快.

This solution uses basic bit shifting and bit extraction. Using bit operations should be faster than using higher level operations such as exponentiation and multiplication.

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

The fundamental solution is much the same as in the special case, since only one integer's maximum bit length is required in either case. The tests, however, are not.

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: https://stackoverflow.com/a/54164324/
    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)

这篇关于将具有不同位长的两个大整数可逆编码为一个整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！