具有随机移位加密的二进制字符串
你好 我的二进制字符串长度为 n。我的目标是字符串中的所有位都等于“1”。 我可以翻转我想要的字符串的每一位，但是翻转字符串的位后，它会进行随机循环移位。（移位长度均匀分布在 0...n-1 之间）
我无法知道什么是状态该位既不是最初的，也不是在过程中间的，我只知道它们何时全部为“1”
据我所知，应该有一些策略来保证我在该字符串的真值表中进行所有排列。
谢谢
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)
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
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
翻转位 1，直到所有位都设置为 1。如果不测试这些位，我看不出有什么更快的东西。
Flip bit 1 until all are set to 1. I don't see there being anything faster without testing the bits.
Georg 有最好的答案，如果字符串随机移动（我假设 0..n 位均匀分布），他总是翻转第一位的策略迟早会成功。
不幸的是，该策略可能需要很长时间，具体取决于字符串的长度。
被设置为 1 的位数的期望值平均为 n/2，因此位翻转成功的概率为 0.5，每设置一位，概率就会减少 1/n。
该过程可以被视为马尔可夫链，其中处于状态 0xff...ff 的概率计算所有位的设置，从而可以计算达到该状态所需的平均试验次数。
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.