двоичная строка со случайной сдвиг-криптографией

Question

Здравствуйте, у меня длина двоичной строки n. Моя цель состоит в том, чтобы все биты в строке были равны "1".Я могу перевернуть каждый бит строки, который мне нужен, но после переворачивания битов строки происходит случайное круговое смещение (длина смещения равномерно распределена между 0 ... n-1)

У меня нет возможностиЯ знаю, что такое состояние бита не в начале или в середине процесса. Я знаю только, когда все они равны «1»

. Как я понимаю, должна быть какая-то стратегия, которая гарантирует мне, что я делаю все перестановки в правдетаблица этой строки.

Спасибо

Answer 1

Переверните бит 1, пока все не будут установлены в 1. Я не вижу ничего более быстрого без тестирования бит.

Answer 2

У Георга лучший ответ, если строка смещена случайным образом (я предполагаю, что на 0 ... n бит равномерно распределена), его стратегия всегда переключать первый бит рано или поздно будет успешной.

К сожалению, эта стратегия может занять очень много времени в зависимости от длины строки.

Ожидаемое значение числа битов, которое устанавливается в 1, будет в среднем n / 2, поэтому вероятность того, что переключение битов будет успешным, составляет 0,5, для каждого устанавливаемого бита вероятность уменьшается на 1 / n.

Процесс можно рассматривать как цепочку Маркова , где вычисляется вероятность нахождения в состоянии 0xff ... ff, где установлены все биты, и, таким образом, число попыток в среднем, необходимых для достижения этого состояния можно рассчитать.