binary string with random shift-cryptography
Hello I have a binary string length of n.My goal is that all bit in string will be equal to "1". I can flip every bit of the string that I want but after fliping the bits of the string it does random circular shift.(shift length evenly distributed between 0...n-1开发者_JAVA百科)
I have no way to know what is a state of the bit not initianly nor in middle of process I only know when they all is "1"
As I understand there should be some strategy that guarantees me that I do all the permuatations in truth table of this string.
Thank you
Flip bit 1 until all are set to 1. I don't see there being anything faster without testing the bits.
Georg has the best answer, if the string is shifted randomly (I assume by 0..n bits evenly distributed) his strategy of always flipping the first bit will sooner or later succeed.
Unfortunately that strategy may take very long time depending on the length of the string.
The expected value of the number of bits being set to 1 will be n/2 in average, so the probability that a bit flip will be successful is 0.5, for each bit being set that probability decreases by 1/n.
The process could be viewed as a markov chain where the probability for being at state 0xff...ff where all bits are set is calculcated and thus the number of trials in average required to reach that state can be calculated.
精彩评论