Как представить битовые последовательности числами и отфильтровать те, что содержат подряд идущие единицы

Что проверяют

Умеете ли вы думать о битовой последовательности как о числе и пользоваться побитовыми операциями вместо работы со строками. Следом обычно просят не фильтровать, а сразу построить все подходящие последовательности длины n или посчитать их количество.

Как отвечать

Представление:

• из строки в число: int("1011", 2) даёт 11, обратно format(x, "b") или bin(x)[2:];
• фиксированная длина: при переводе в число ведущие нули теряются, поэтому длину n хранят отдельно и печатают через format(x, f"0{n}b");
• размер: целые в Python произвольной длины и не переполняются, а для массовой обработки последовательностей до 64 бит подходят массивы numpy.uint64.

Ключевой приём: сдвиг на один разряд ставит каждый бит напротив соседа, поэтому x & (x >> 1) не равно нулю ровно тогда, когда в числе есть две единицы подряд. Фильтр получается в одну строку:

valid = [x for x in range(1 << n) if x & (x >> 1) == 0]

В Python & связывает сильнее ==, так что условие читается верно, но скобки для ясности не помешают. Для трёх единиц подряд условие x & (x >> 1) & (x >> 2), в общем случае повторяют y &= y >> 1 нужное число раз.

Дальше покажите, что понимаете сложность. Перебор стоит O(2^n), а подходящих последовательностей F(n+2), это числа Фибоначчи: к корректной строке можно дописать 0 всегда, а 1 только после 0. Поэтому при больших n подходящие строят напрямую обходом с возвратом, а количество считают динамикой за O(n).

Где спотыкаются

Остаются в строках и проверяют "11" in s. Для строк это правильно, но задача про числа: теряется компактное хранение, векторизация через numpy и тот самый приём, ради которого задачу дают.

Теряют ведущие нули: "0101" и "101" становятся одним числом 5, и без хранения длины исходную строку уже не восстановить.

Перебирают 2^n при n = 40. Это около триллиона итераций, и интервьюер ждёт, что вы заметите это сами и перейдёте к генерации или подсчёту.