Существует ли биекция между какими-либо отдельными 4-битными строками и всеми 2-битными строками?

Question

Позвольте мне привести пример, давайте рассмотрим строки: 1000 0101 0111 0000

и полный диапазон 2-битных строк: 00 01 10 11

Мне интересно, есть ли функция, которая имеет инверсию и которая отображает 4-битную строку в 2-битные строки.

Answer 1

Для случая 4 4 битов у вас есть 16 ** 4 или 65536 случаев, это будет отображаться в 8 2 битных ячейках, так что это будет тривиальной проблемой. Однако, если вы переформулируете свою проблему как биективное отображение пространства всех строк, состоящих из 4 битов на 2 бита на байт, это будет другой проблемой, и да, у которой есть решение.

Простое решение - посмотреть на отображение бесконечного нечетного двоичного пространства строк каждого типа шаблона. У бесконечной нечетной строки есть последняя на конечном расстоянии от начала, что вы делаете, вы начинаете писать биты, когда они появляются, у вас есть один флаг, если он установлен, и вы сделали последний байт (2 или 4 бита, в зависимости от того, какое значение вы используете) вы пишете 1000 ... если флажок снят, вы пишете 000 ..., поскольку в расширении был один, который является последним "1".

• для 2-битного набора
• 00 устанавливает флаг
• 10 ничего не делает для пометки

• остальные 01 11 снимают флаг

• для 4-битного набора

• 0000 устанавливает флаг
• 1000 ничего не делает для пометки
• все остальные содержат по крайней мере 1 или более и снимите флажок

преобразование 1000 0101 0111 0000 в прямую копию 100001010111000010000 ... обратите внимание на хвост 100 .. так как флаг установлен. Если вы делаете обратное для 2-х бит, установите флаг проходит через многие государства, но 1000 .. в конце части флага, так что в Установив 2 бита, вы получите 10 00 01 01 01 11 00 00 нет ничего сложного 8 байт

но при конвертации 1000 0101 0111 0100 вы получите 1000010101110000 ... при просмотре 2-битного набора вы получите 10 00 01 01 01 11 10 что на 2 бита меньше на 7 байт

для эта биекция из 4 битов, установленных в 2 бита, всегда будет либо 2n байтов для байта двух байтов или 2n-1 байтов, где n число 4-битных байтов.

Этот метод отображения на бесконечные нечетные файлы работает для биективного преобразования любой строки член бесконечного набора любого количества байтов на байт, даже если число биты, составляющие байт, меняются в зависимости от n.

Answer 2

Количество переходов из набора из n элементов в другой набор из n элементов равно n!

Рассмотрим каждый элемент назначения последовательно и выберите соответствующий элемент источника. Для первого вы можете выбрать среди n. Во-вторых, вы можете выбрать среди (п-1). ...

Вы хотите биекцию между наборами из 4 элементов, поэтому у вас есть 4! = 24 возможных функций.

00 будет отображаться на 1000 в шести из них (3!), На 0101 в шести из них и т. Д.

Я не уверен, что это отвечает на ваш вопрос, но я так понимаю.