4ビットからのほとんどのバイナリの組み合わせ、ビットごとに1つの変更

StackOverflow https://stackoverflow.com/questions/450617

質問

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時の範囲内にあることを知っています。可能な限り最小の範囲を取得できるようにしたい。私が得ることができる最小の範囲は何ですか？

役に立ちましたか？

解決

  1. 4ビットがあります。
  2. 各ビットは状態を1回だけ変更できます。
  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時、正午-午前0時に設定すると、出力から3時間の期間を判別できます。代わりに、視覚的な出力にワイヤを差し込むことをお勧めします。

他のヒント

グレーコードが必要です。 <！> quot; nビットグレーコードの構築<！> quot;については、半分ほど下を見てください。

このような制限があるすべての可能なビットパターンを循環させることは不可能だと思います。

nビットのアイデアがある場合、既に反転したビットを反転する前に、合計（n + 1）状態を循環できます。

たとえば、3ビットの例では、111で始まる場合、次のようになります

111
110
100
000

そして、新しい状態を取得するために、すでに反転したものを反転させる必要があります。

目覚まし時計の例に基づいて、開始した組み合わせを完了する必要があり、各ビットは一度だけオンとオフを繰り返すことができると仮定します、例えば

  

0000-<！> gt; 0001-<！> gt; 0011-<！> gt; 0111-<！> gt; 1111   -<！> gt; 1110-<！> gt; 1100-<！> gt; 1000-<！> gt; 0000

ステップ数はビット数の2倍なので、4ビットでは現在の時刻を3時間の範囲内に収めることができます。

各ビットを一度だけ変更したいですか？

いいね：

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

その場合、単純なカウンターを使用して、各反復ごとにデルタを2倍する（または左にシフトする）ことができます。

Gamecatが正しくあなたを見つけたら、 ビットマスク値は次のようになります。

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

または、シフトを使用：  （1 <！> lt; <！> lt; i）-0のiに対して1 ..

<！> quot;ビットの状態がすべての反復を通じて一度だけ変更されるアルゴリズムが必要です<！> quot;

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

質問が<！> quot;生成可能なシーケンスの数<！> quot;の場合：

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

そうでない場合、16の初期状態が考えられます。

注文は重要ですか？

はいの場合、4つあります！ =最初に反転するビットを選択する24の可能な方法。

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

元の質問を振り返って、私はあなたの意味を理解していると思います

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

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

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

誰かが計算を知っている場合

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

ここでは、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回だけ反転できます。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top