1

我有 4 个二进制位

Bit 3  Bit 2  Bit 1  Bit 0

通常答案很简单：2^4，或 16 种不同的组合；它看起来像下面这样：

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

但是，LSB（位 0）每次迭代都会改变状态。

我需要一种算法，其中位的状态在所有迭代中只改变一次；即，我需要我所有的位都像 MSB（位 3）一样工作。

我怎样才能做到这一点？

编辑

似乎大多数人都认为只有 5 种可能的解决方案。然而，这假设有一个值的起点和一个终点。这没关系，所以我将给出一个真实世界的场景来更好地解释。

假设我有一个数字闹钟，可以提供 4 个输出。每个输出都可以被编程为在某个时间打开和在某个时间关闭，并且可以彼此独立地进行编程，例如。我可以将输出 1 编程为在凌晨 1 点打开并在凌晨 3 点关闭，而我可以将输出 2 编程为在下午 7 点打开并在凌晨 2 点关闭。每个输出可以保持多长时间没有限制。

现在我想把这个闹钟挂在电脑上，尽可能接近当前的正确时间。例如，如果时钟显示时间是下午 2:15，我的电脑就知道闹钟在下午 12 点到下午 6 点的范围内。我希望能够获得尽可能小的范围。我能得到的最小范围是多少？

4

9 回答 9

12
  1. 有 4 位。
  2. 每个位只能改变一次状态。
  3. 对于每个新值，至少有一个位必须从先前的值改变状态。

因此，您最多可以有 4 个状态更改，以及最多 5 个不同的值。

例子：

0000 -> 0001 -> 0011 -> 0111 -> 1111

编辑：

很好，让我们重述你的意思，而不是你所说的。

  1. 有 4 位。
  2. 每个位只能改变两次状态。（一次从 0 到 1，一次从 1 到 0）
  3. 对于每个新值，至少有一个位必须从先前的值改变状态。

因此，您最多可以有 8 个状态更改，以及最多 8 个不同的值（因为最后一次状态更改必然会使所有位恢复到初始状态）

例子：

0000 -> 0001 -> 0011 -> 0111 -> 1111 -> 1110 -> 1100 -> 1000 -> 0000

因此，通过将输出设置为：上午 3 点 - 下午 3 点、上午 6 点 - 下午 6 点、上午 9 点 - 晚上 9 点和中午 - 午夜，您可以从输出中确定是哪个 3 小时时段。我建议将电线插入视觉输出。

于 2009-01-16T15:01:35.237 回答
7

你想要一个格雷码。往下看“构造一个 n 位格雷码”。

于 2009-01-16T14:56:20.707 回答
3

我相信不可能通过这种限制循环所有可能的位模式。

如果您有一个 n 位的想法，您可以在必须翻转您已经翻转的位之前循环总共 (n+1) 个状态。

例如，在一个 3 位的例子中，如果你从 111 开始，你会得到

111
110
100
000

然后你被迫翻转你已经翻转的一个以获得新的状态。

于 2009-01-16T15:01:16.047 回答
1

根据您的闹钟示例，我假设您需要完成您开始的组合，并且每个位可以循环打开然后关闭一次，例如

0000 -> 0001 -> 0011 -> 0111 -> 1111 -> 1110 -> 1100 -> 1000 -> 0000

步数是位数的两倍，因此使用 4 位可以将当前时间控制在 3 小时范围内。

于 2009-01-16T16:13:22.237 回答
0

您希望每个位只更改一次吗？

像：

0000 -> 0001 -> 0011 -> 0111 -> 1111

在这种情况下，您可以使用一个简单的计数器，每次迭代（或左移）将增量乘以 2。

于 2009-01-16T14:57:48.643 回答
0

如果 Gamecat 正确理解了您，您的位掩码值将是：

 1 - 1 
 2 - 1 
 4 - 1
 8 - 1
 16 - 1
 etc.
 2^i - 1

或者，使用移位： (1 << i) - 1 for i in 0..

于 2009-01-16T15:07:31.713 回答
0

“我需要一种算法，其中一点的状态在所有迭代中只改变一次”

如果从字面上理解上述陈述，那么每次迭代只有五个状态，如其他帖子中所述。

如果问题是“可以生成多少个可能的序列？”，那么：

第一个状态总是0000吗？

如果没有，那么您有 16 个可能的初始状态。

顺序重要吗？

如果是，那么你有 4 个！= 24 种可能的方式来选择首先翻转哪些位。

因此，这总共可以生成 16*24 = 384 个可能的序列。

于 2009-01-16T15:11:01.660 回答
0

这是一个示例，说明如何避免仅翻转一次。不知道系统的所有参数，很难给出一个准确的例子，但无论如何这里有一个。

char bits = 0x05;
flipp_bit(char bit_flip)
{
    static char bits_flipped=0;
    if( (bits_flipped & bit_flip) == 0)
    {
        bits_flipped |= bit_flip;
        bits ^= bit_flip;
    }
}

使用此功能进行翻转将只允许对每一位进行一次翻转。

于 2009-01-16T15:12:10.940 回答
0

回顾最初的问题，我想我明白你的意思

简单地说，根据可能的位组合的数量，您可以用来对时钟进行编程的最小位数是多少

第一个问题是需要多少序列。

60Secs x 60 Mins x 24hrs = 86400（需要组合）下一步是计算需要多少位才能产生至少 86400 个组合

如果有人知道计算

how many bits can produce 86400 combinations then thats your answer. hopefully there is a formula online somewhere for this calculation

于 2009-12-23T20:36:37.737 回答