длина непрерывных битов 1 потока с последующим 0

Question

Был вопрос на собеседовании, поэтому искали неочевидные решения.

Скажем, есть большой поток 1111 ... 111100000 ... 000

найти длину (число) 1.

Вы можете предположить, что здесь 1 установленный бит.

Как это изменится, если 1 будет символом, скажем, как aaa..aaaabbbb ... bbbbb

Одним из решений, которое я мог бы предложить, было посмотреть 1-й бит / символ, затем удвоить интервал, например, затем посмотреть 3-й, затем 7-й и так далее. когда вы нажимаете 0 или другой символ, возвращайтесь к последней позиции, снова используя «разделяй и властвуй».

Answer 1

Если у вас есть произвольный доступ к потоку и его длина известна, вы можете сделать это с помощью варианта бинарного поиска в O (log n).

В качестве альтернативы вы можете использовать 0x1 и, если ноль, счетчик приращения и сдвиг вправо на 1. Или, вы можете проверить, являются ли целые байты (слова, двойные слова, четверные слова и т. д.) ненулевыми, чтобы быстрее найти блок, с которого начинаются единицы.В любом случае, это O (n).

Answer 2

Если вы хотите проходить поток битов линейно, вы можете обработать его в 32-битных блоках, выполнив побитовое И с 0xFFFFFFFF (все 1 с) и соответственно обновив ваш счетчик.

Это использует тот факт, что современные процессоры, как правило, могут выполнять побитовые операции над 32-битными словами как одно атомарное действие.

Если результат AND равен 0xFFFFFFFF, то вы знаете, что потенциально может быть больше битов, и, следовательно, должны проверить следующее 32-битное слово. В противном случае вы просто увеличиваете счетчик и прекращаете цикл.

Answer 3

двоичный поиск, чтобы найти индекс, в котором установлен i-й бит, а (i + 1) - нет.добавьте специальный случай, когда первый бит не установлен и последний бит установлен, и все готово