c - 除以N的二进制时钟序列算法？

Question

我不太确定如何描述我的意思，所以让我尝试通过示例进行解释(请耐心等待)。

当你简单地增加一个整数时，你会得到一个像这样的二进制序列(让我们假设这个问题是 8 位):

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0
0 0 0 0 0 0 1 1
0 0 0 0 0 1 0 0
0 0 0 0 0 1 0 1
0 0 0 0 0 1 1 0 
0 0 0 0 0 1 1 1
0 0 0 0 1 0 0 0
0 0 0 0 1 0 0 1
0 0 0 0 1 0 1 0
0 0 0 0 1 0 1 1
0 0 0 0 1 1 0 0
0 0 0 0 1 1 0 1
0 0 0 0 1 1 1 0 
0 0 0 0 1 1 1 1
0 0 0 1 0 0 0 0
0 0 0 1 0 0 0 1
0 0 0 1 0 0 1 0
0 0 0 1 0 0 1 1
0 0 0 1 0 1 0 0
0 0 0 1 0 1 0 1
0 0 0 1 0 1 1 0 
0 0 0 1 0 1 1 1
0 0 0 1 1 0 0 0
0 0 0 1 1 0 0 1
0 0 0 1 1 0 1 0
0 0 0 1 1 0 1 1
0 0 0 1 1 1 0 0
0 0 0 1 1 1 0 1
0 0 0 1 1 1 1 0 
0 0 0 1 1 1 1 1
[ ... etc ... ]

一种可视化的方法是，每一列代表一个“时钟”。每个时钟/列的频率是其右邻居的一半。

所以最右边的时钟有一个0接下来是一个 1等。下一个时钟有两个 0 s 后面跟着两个 1等等等等...

我对二进制字符串序列感兴趣，其中每个时钟都是其邻居的整数除法。

所以最右边的时钟仍然是 0 , 一 1 ，下一个时钟还剩两点 0 s，两个1 s，但第三个时钟是三 0 s 和三个 1等

而不是 /1 /2 /4 /8 /16 ...现在是/1 /2 /3 /4 /5 ... .

序列现在看起来像这样:

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0
0 0 0 0 0 1 1 1
0 0 0 0 1 1 0 0
0 0 0 1 1 1 0 1
0 0 1 1 1 0 1 0
0 1 1 1 1 0 1 1
1 1 1 1 0 0 0 0
1 1 1 1 0 1 0 1
1 1 1 0 0 1 1 0
1 1 1 0 0 1 1 1
1 1 0 0 1 0 0 0
1 1 0 0 1 0 0 1
1 0 0 0 1 0 1 0
1 0 0 1 1 1 1 1
0 0 0 1 0 1 0 0
0 0 0 1 0 1 0 1
0 0 1 1 0 0 1 0
0 0 1 1 0 0 1 1
[ ... etc ... ]

问题:是否有一种操作/算法可以给我 i 的值给定值 i-1 ？

换句话说，假设我处于第四步 ( 0 0 0 0 0 1 1 1 )。我可以对此数字执行一些操作来获取第五步( 0 0 0 0 1 1 0 0 )的值，对于任何其他步骤也类似？

在除以 2 的情况下，您只需增加数字( i++ )，但在除以 N 的情况下，我似乎无法找出从一个到下一个的类似方法。我是否遗漏了一些明显的东西？

我尝试将排序转换为十进制，但该模式是 0, 1, 2, 7, 12, 29, 58, etc这对我来说并不明显。

我现在这样做的强力方法是，我有一个计数器数组(每个列/时钟一个)，并且当达到相应列的“周期”时，我独立地重置每个计数(因此 2 表示第一列，下一列为 3，依此类推)。但感觉很丑。

我很乐意直接在号码上执行此操作，而不需要一系列计数器。这可能吗？这是已知序列吗？老实说，我什至不知道该谷歌什么。我将不胜感激任何有关此事的线索。我很高兴在一些指导下进入兔子洞。

更新

根据 @borrible 的观察， i-1 有多个值对于给定的i所以事实证明我原来问题的解决方案是不明确的。所以我将扩展我的问题以允许 i作为输入(除了 i-1 th 值。

Answer 1

在不知道i的情况下，如果给定序列唯一地暗示i(对位序列的数量取模)，您就只能生成该序列的后继。如果不是这种情况，则给定序列的后继是不明确的。

让我们考虑 3 位的前几个序列:

0 0 0
0 0 1
0 1 0
1 1 1
1 0 0
1 0 1
0 1 0
0 1 1

请注意，0 1 0 后继的是 1 1 1 和 0 1 1；即它是不明确的。给定 0 1 0 但不给定 i，您无法推断出下一个序列。您可以在 0 1 1 1 等 4 位序列中看到类似的歧义...

换句话说，在不知道i的情况下，你的问题通常无法解决。