Проблему проще пояснить на примере :
Даны числа "кирпичики" 0-15 ( ниже 2а из них в бинарной записи )
0001 1011
Дано некое очень большое число состоящее из единиц ( те вида 2^n - 1 ). Например 2^32-1 = 11111111111111111111111111111111
Для кирпичиков разрешена операция сдвига и сложения если ни одна из единиц не пересекается. Вопрос : Какие из чисел кирпичиков после применения операций будут наиболее похожи на данное число. А точнее как определить, тестовый "кирпичик" образует сдвигами последовательность единиц или нет?
Например берем 0001, сдвигами и оп ИЛИ можно получить 00011, 000111 и тд. до 0001..1. Следовательно кирпичик похож ( краевые эффекты не в счет ).
Теперь возьмем 1011, сдвигами можем получить 101110111011, и тд. Следовательно кирпичик не похож (есть 0и).
Приведенные числа маленькие и их тестировать просто, но если числа из десятков разрядов, то это становиться проблемой. Способ который сейчас используется это перебор сдвигов и рекурсивное вкладывание с проверкой на конфликты.
|