Обратимое кодирование двух больших целых чисел разной длины в одно целое

Question

Я хочу закодировать два больших целых числа, возможно, различной максимальной длины в битах в одно целое число. Первое целое число подписано (может быть отрицательным), а второе - без знака (всегда неотрицательно). Если длина в битах равна m и n соответственно, длина в битах возвращаемого целого числа должна быть меньше или равна m + n.

Просто n (но не m) заранее известно и исправлено. В качестве примера решение будет использовано для объединения подписанной наносекундной метки времени из 61+ битов и 256 битов беззнаковой случайности для формирования уникального идентификатора со знаком 317+ бит.

Я использую последний Python. Существует связанный ранее существующий вопрос, который решает эту проблему в особом случае , когда m == n.

Answer 1

Поскольку n исправлено, проблема тривиальна: кодируйте ( a , b ) как a • 2 ^N + * * 1013 б .

Если 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, сдвиг влево на n битов и либо вычитание / побитовое XOR из / с закодированным числом, чтобы получить единицу длины n),
• ИЛИ вам следует отдельно / где-то запоминать одно из чисел (надеюсь, оно является обычным для пользователя?) И просто побитово-XOR числа (для обратного, просто побитовый результат XOR с сохраненным числом); бонусные баллы, если это является обычным для пользователя, любой дополнительный кодированный идентификатор на пользователя после первого добавляет только максимум (m, n) бит данных к потребностям хранилища.

Answer 3

Это решение использует базовое смещение бит и извлечение бит. Использование битовых операций должно быть быстрее, чем использование операций более высокого уровня, таких как возведение в степень и умножение.

Фундаментальное решение во многом такое же, как и в особом случае, поскольку в любом случае требуется максимальная длина в битах только одного целого. Тесты, однако, не являются.

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)