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) は反復ごとに状態が変化します。

すべての反復でビットの状態が 1 回だけ変化するアルゴリズムが必要です。つまり、すべてのビットが MSB (ビット 3) のように動作する必要があります。

これどうやってするの？

編集

ほとんどの人は、可能な解決策が 5 つしかないことに収束しているようです。ただし、これは値の開始点と終了点があることを前提としています。これは問題ではないので、よりよく説明するために実際のシナリオを示します。

4 つの出力を提供するデジタル目覚まし時計があるとします。各出力は、特定の時間にオンになり、特定の時間にオフになるようにプログラムでき、互いに独立してプログラムできます。出力 1 は午前 1 時にオンになり、午前 3 時にオフになるようにプログラムでき、出力 2 は午後 7 時にオンになり、午前 2 時にオフになるようにプログラムできます。各出力をオンにしておくことができる時間に制限はありません。

今度は、この目覚まし時計をコンピューターに接続して、現在の正確な時刻にできるだけ近づけたいと考えています。たとえば、時計が午後 2 時 15 分である場合、コンピュータはアラームが午後 12 時から午後 6 時の範囲内にあることを認識します。可能な限り最小の範囲を取得できるようにしたい。私が得ることができる最小の可能な範囲は何ですか?

4

9 に答える 9

12
  1. 4 ビットあります。
  2. 各ビットは一度だけ状態を変更できます。
  3. 新しい値ごとに、少なくとも 1 つのビットの状態が前の値から変更されている必要があります。

したがって、最大 4 つの状態変化と、最大 5 つの異なる値を持つことができます。

例：

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

編集：

そうですね、あなたの言っていることからではなく、あなたの言いたいことから言い直しましょう。

  1. 4 ビットあります。
  2. 各ビットは2 回だけ状態を変更できます。(0 から 1 に 1 回、1 から 0 に 1 回)
  3. 新しい値ごとに、少なくとも 1 つのビットの状態が前の値から変更されている必要があります。

したがって、最大で 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

あなたはグレイコードが欲しい。"Constructing an n-bit gray code" の半分ほど下を見てください。

于 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

ステップ数はビット数の 2 倍なので、4 ビットで現在の時刻を 3 時間以内に取得できます。

于 2009-01-16T16:13:22.237 に答える
0

元の質問を振り返ってみると、あなたの言いたいことは理解できたと思います

可能なビットの組み合わせの量に基づいて、クロックをプログラムするために使用できるビットの最小量は何ですか

最初の質問は、必要なシーケンスの数です。

60 秒 x 60 分 x 24 時間 = 86400 (必要な組み合わせ) 次のステップは、少なくとも 86400 の組み合わせを生成するために必要なビット数を計算することです。

誰かが計算を知っていれば

何ビットで 86400 の組み合わせを生成できるか、それがあなたの答えです。うまくいけば、この計算のためのオンラインのどこかに式があります

于 2009-12-23T20:36:37.737 に答える
0

各ビットを 1 回だけ変更しますか?

お気に入り：

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

「すべての反復でビットの状態が 1 回だけ変化するアルゴリズムが必要です」

上記のステートメントを文字通りに解釈すると、他の投稿で説明されているように、反復ごとに 5 つの状態しかありません。

質問が「いくつの可能なシーケンスを生成できるか?」である場合、次のようになります。

最初の状態は常に 0000 ですか?

そうでない場合、16 の可能な初期状態があります。

順序は重要ですか？

はいの場合は、4 つです。= 最初に反転するビットを選択する 24 通りの方法。

したがって、これにより、生成できる合計 16*24 = 384 の可能なシーケンスが得られます。

于 2009-01-16T15:11:01.660 に答える
0

これは、ビットが 1 回だけ裏返されるのを防ぐ方法の例です。システムのすべてのパラメーターを把握していないため、正確な例を示すのは簡単ではありませんが、ここではその例を示します。

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;
    }
}

この関数で反転すると、各ビットで 1 つの反転のみが許可されます。

于 2009-01-16T15:12:10.940 に答える