Вложимость бинарного представления целых

[dmitr.manohin]

Проблему проще пояснить на примере :

Даны числа "кирпичики" 0-15 ( ниже 2а из них в бинарной записи )

0001
1011

Дано некое очень большое число состоящее из единиц ( те вида 2^n - 1 ).
Например 2^32-1 = 11111111111111111111111111111111

Для кирпичиков разрешена операция сдвига и сложения если ни одна из единиц не пересекается.
Вопрос : Какие из чисел кирпичиков после применения операций будут наиболее похожи на данное число.
А точнее как определить, тестовый "кирпичик" образует сдвигами последовательность единиц или нет?

Например берем 0001, сдвигами и оп ИЛИ можно получить 00011, 000111 и тд. до 0001..1. Следовательно кирпичик похож ( краевые эффекты не в счет ).

Теперь возьмем 1011, сдвигами можем получить 101110111011, и тд. Следовательно кирпичик не похож (есть 0и).

Приведенные числа маленькие и их тестировать просто, но если числа из десятков разрядов, то это становиться проблемой. Способ который сейчас используется это перебор сдвигов и рекурсивное вкладывание с проверкой на конфликты.

[mihaild]

Т.е. вопрос в том, можно ли из данного числа получить битовыми сдвигами влево и битовым или (которое можно применять только к числам, которые побитовое и которых нулевое) получить данное число? Непонятно, зачем тут нужен перебор.

[dmitr.manohin]

Вообще вы наверное правы, достаточно сдвигов