Существует ли общий подход к оптимизации побитовых выражений, различающих два произвольных набора целых чисел?
Для контекста мне нужно написать тест для целого числа от 0 до 7 включительно, который будет иметь значение true для {1,3,4,6} и false для {0,2,5,7}. Я пару минут думал о том, может ли существовать короткое выражение, объединяющее несколько побитовых операций, которое выполнило бы эту работу (например, аналогично тому, как n & 1 будет работать с {1,3,5,7}), но ни одно из них мне не бросилось в глаза.
На практике здесь нет острой необходимости использовать побитовую арифметику, что-то вроде переключателя или таблицы поиска будет работать нормально, но это заставило меня задаться вопросом, существует ли детерминированный способ найти такое выражение: дать ненулевой результат, когда оценивается по числам из первого набора и нулю по числам второго набора, используя только побитовые and, or, not и xor (так что, например, нет логических && или ==)
У меня нет математической подготовки, чтобы обосновать это, но кажется разумным предположить, что можно написать какое-то выражение «грубой силы», независимо от верхней границы, где каждый случай оценивается отдельно, соединенный вместе | , но есть ли более эффективный подход: упростить реализацию «наихудшего случая» или создать ее с нуля?
Ответы 3
В данном конкретном случае оптимальным решением является справочная таблица в один байт, например (1 << x & (1 << 1 | 1 << 3 | 1 << 4 | 1 << 6)) != 0. Это более эффективно, чем любая комбинация and, or, not и xor для вычисления одного и того же.
Кстати, компиляторы C/C++/Rust умны. Учитывая assert!(x >= 0 && x <= 7);, Rusc генерирует практически оптимальный код из !matches!(x, 0 | 2 | 5 | 7) и почти так же хорошо из matches!(x, 1 | 3 | 4 | 6).
Вы можете попробовать использовать супероптимизатор . К сожалению, я не могу найти тот, который можно было бы легко использовать для этого примера. Если я взломаю тот, который написал, я получу
(x & 1) != (x >> 2)
если я позволю ==, что, вероятно, будет самым быстрым выражением на практике, и
((x >> 2) ^ x) & 1
если я этого не сделаю.
В общем, это невозможно. Ограничение только на побитовое и/или нет, а также xor означает, что каждый бит результата зависит только от этого бита входных данных.
Предположим, мы хотим отличить {1, 2} от {0, 3} с помощью такой функции f, где результат будет ненулевым для {1, 2} и нулевым для {0, 3}.
Результаты f(0) и f(3) должны быть 0. Поскольку биты не могут влиять на другие биты, f(1) должно быть 1 и f(2) должно быть 2. Учитывая результаты f(1) и f(2), результат f(3) должен иметь младший значащий бит, равный младшему значащему биту f(1), а следующий за ним значащий бит равен следующему за наименее значащим биту f(2). Следовательно, f(3) должно быть 3, что означает, что f не может различить два набора должным образом.
Альтернативное объяснение основано на количестве таких функций, которые могут существовать. Бит результата может быть 0 или 1 для входа 0 и независимо 0 или 1 для входа 1, что дает четыре возможности для каждого бита. Для трехбитных чисел это означает, что существует 4 * 4 * 4 = 64 возможностей, что меньше, чем 256 возможных подмножеств набора из восьми элементов. Следовательно, должно быть не менее 256 - 64 = 192 подмножеств, которые не может быть выделена такой функцией.