隨機移位加密的二進制字符串

你好我有一個二進制字符串長度爲n。我的目標是字符串中的所有位都等於「1」。我可以翻轉我想要的字符串的每一個位，但是在對字符串的位進行位移後，它會進行隨機循環移位（移位長度均勻分佈在0 ... n-1之間）隨機移位加密的二進制字符串

我無法知道什麼是這個位不是初始狀態，也不是在過程中間我只知道他們什麼時候都是「1」的狀態

據我所知，應該有一些策略保證我做這個真值表中的所有permuatations串。

謝謝

2010-11-04 Evgeniy

如果所有的位都是1，那麼這只是'0xfffffff ...'，這可能不是你想要的。你能再詳細一點嗎？目前還不清楚... – 2010-11-04 08:51:20

我不知道初始字符串值 – Evgeniy 2010-11-04 08:55:45

隨機循環移位是什麼意思？移位長度是否均勻分佈在0 ... n-1之間？ – Ernelli 2010-11-04 08:57:10

翻轉位1，直到所有被設置爲1。我看不出有任何物件無需測試位快。

2010-11-04 08:53:58

我不認爲它的最快戰略。可能會有一種情況，我會花很長時間才能得到我想要的結果。 – Evgeniy 2010-11-04 09:01:45

@Evgeniy：沒錯。甚至可能是你永遠無法達到這種情況。但看到隨機變化，我懷疑有一種方法可以讓它變得更快，除非你有更多的信息。 – 2010-11-04 09:27:55

Georg有最好的答案，如果字符串隨機移動（我假設0..n位均勻分佈），他總是翻轉第一位的策略遲早會成功。

不幸的是，策略可能需要很長時間，這取決於字符串的長度。

被設置爲1的位數的期望值將平均爲n/2，所以位翻轉將成功的概率是0.5，對於設置的每個位，該概率減少1/n。

該過程可以看作是markov chain，其中處於狀態0xff ... ff的所有位被設置的概率被計算並因此可以計算達到該狀態所需的平均試驗次數。

2010-11-04 11:06:54 Ernelli

回答