Какой алгоритм можно предложить для решения задачи с битовыми последовательностями

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

Формулировка размыта намеренно: интервьюер смотрит, уточните ли вы задачу и знаете ли базовые битовые приёмы. Следом дают конкретику, например найти число без пары в массиве или самую длинную серию единиц, и спрашивают сложность.

Как отвечать

Сначала уточните вход: число, строка вида "0110" или поток байтов, бывают ли отрицательные, какие размеры. Затем покажите приёмы, которые закрывают большинство задач:

• подсчёт единиц: с Python 3.10 есть int.bit_count(), раньше писали bin(n).count("1"). Руками это приём Кернигана n &= n - 1: он снимает младшую единицу и работает за число единиц, а не за число битов;
• XOR: a ^ a == 0, поэтому functools.reduce(operator.xor, nums) находит единственный элемент без пары за O(n) и O(1) памяти. Расстояние Хэмминга считается так же: (a ^ b).bit_count();
• маски: n & (n - 1) == 0 проверяет степень двойки при n > 0, x & -x выделяет младший бит, подмножества из k элементов перебираются масками от 0 до 2**k - 1;
• серии: самую длинную последовательность единиц ищут одним проходом со счётчиком, а вариант «можно перевернуть один ноль» решается скользящим окном, в котором не больше одного нуля.

Для больших последовательностей подойдут bytes и int.from_bytes(), в NumPy np.unpackbits и векторные операции. Цикл по битам на чистом Python на миллионах элементов будет медленным.

Всегда называйте сложность и проверяйте крайние случаи: ноль, одна единица, все единицы.

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

Забывают про отрицательные числа. В Python int не ограничен по длине, -1 >> 1 снова равно -1, и цикл while n: n >>= 1 не закончится. Нужна маска вроде n & 0xFFFFFFFF.

Путают ^ со степенью. В Python это XOR, а степень пишется **.

Сразу пишут код, не уточнив, что за последовательность. Решение для числа и для строки из нулей и единиц выглядит по-разному.