Предлагая самый простой способ для преобразования битового массива 1 в битовый массив 2
Рассмотрим множество всех битовых массивов длины n. Теперь рассмотрим набор всех функций 1-к-1, которые отображаются из этого набора в этот набор.
Теперь выберите одну функцию из последнего набора. Есть ли алгоритм, чтобы найти "минимальный" способ реализации этой функции? Предположим, что у нас есть доступ только к основным операторам массива битов, таким как AND ИЛИ XOR NOT и левому и правому битовым сдвигам.
Если вам интересно, причина, по которой я этого хочу, заключается в том, что я пишу алгоритм для преобразования порядка битов по z-кривой в порядок битов по гильбертовой кривой. Мой текущий метод заключается в создании справочной таблицы, но я уверен, что есть лучший вариант.
В качестве простого примера, допустим, у меня есть таблица истинности, которая выглядит следующим образом:
00 -> 10
01 -> 01
10 -> 00
11 -> 11
Тогда я должен быть в состоянии вывести это, учитывая строку входного бита input, битовая строка вывода output есть (в синтаксисе Java)
output = ((~input) << 1) ^ input
Вот доказательство в этом случае:
00 -> 11 -> 10 -> 10
01 -> 10 -> 00 -> 01
10 -> 01 -> 10 -> 00
11 -> 00 -> 00 -> 11