Die meisten binären Kombinationen von 4 Bits, mit Einzeländerung pro Bit

Question

Ich habe 4 Binärbits

Bit 3  Bit 2  Bit 1  Bit 0

Normalerweise ist die Antwort einfach: 2 ^ 4 oder 16 verschiedene Kombinationen; und es würde sieht ungefähr wie folgt aus:

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

Um jedoch das LSB (Bit 0) Zustand wechselt jede Iteration.

Ich brauche einen Algorithmus in dem der Zustand eines Bits nur einmal ändert sich durch alle Iterationen; das heißt, ich brauche alle meine Bits wie das MSB (Bit 3) zu handeln.

Wie kann ich das tun?

Bearbeiten

Es scheint, dass die meisten Menschen dort konvergieren nur 5 mögliche Lösungen zu sein. Allerdings setzt dies voraus, ein Ausgangspunkt für den Wert und einen Endpunkt. Dies spielt keine Rolle, so werde ich eine reale Welt Szenario geben, besser zu erklären.

Angenommen ich einen digitalen Wecker, die mir 4 Ausgänge gibt. Jeder Ausgang kann so programmiert werden, zu einem bestimmten Zeitpunkt gehen ein und aus zu einer bestimmten Zeit und ist so programmiert, unabhängig voneinander, zum Beispiel. Ich kann Ausgang programmieren 1 bis um 1 Uhr morgens an und aus um 3 Uhr morgens, während ich Ausgang 2 programmiert werden kann um 7 Uhr geht an und aus um 2 Uhr morgens. Es gibt keine Einschränkungen, wie lange jeder Ausgang bleiben kann.

Jetzt möchte ich auf einen Computer mit diesen Wecker einzuhaken und so nah wie möglich an die aktuelle richtige Zeit. d.h Wenn die Uhr der Zeit ist 02.15 Uhr sagt, mein Computer weiß, dass der Alarm in dem von 12.00 bis 18.00 Bereich zum Beispiel ist. Ich möchte in der Lage, den kleinsten möglichen Bereich zu bekommen. Was ist der kleinste mögliche Bereich kann ich bekommen?

Answer 1

1. Es gibt 4 Bits.
2. Jedes Bit kann den Zustand ändert nur einmal.
3. Für jeden neuen Wert, zumindest eines der Bits Zustand aus dem vorherigen Wert geändert haben muß.

Sie können also höchstens 4 Zustandsänderungen haben und höchstens 5 verschiedene Werte.

Beispiel:

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

Edit:

Sehr gut, fangen wir von neu formulieren, was Sie meinen und nicht von dem, was Sie sagen.

1. Es gibt 4 Bits.
2. kann jedes Bit-Zustand nur dann ändern, zweimal . (Einmal von 0 bis 1, und einmal von 1 auf 0)
3. Für jeden neuen Wert, zumindest eines der Bits Zustand aus dem vorherigen Wert geändert haben muß.

Sie können also höchstens 8 Zustandsänderungen haben und höchstens 8 verschiedene Werte (seit dem letzten notwendigerweise Zustandsänderung alle Bits wieder in ihren Ausgangszustand bringt)

Beispiel:

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

Also, durch Setzen der Ausgänge für: 03.00 bis 15.00, 06.00 bis 18.00, 09.00 Uhr bis 09.00 Uhr und Mittag - Mitternacht, können Sie bestimmen, welche 3 Stunden aus den Ausgängen sind. Ich würde vorschlagen, anstelle Drähte in die visuelle Ausgabe anschließen.

Answer 2

Sie möchten einen Gray Code . Schauen Sie etwa auf halbem Weg nach unten für "Constructing einen n-Bit-Gray-Code".

Answer 3

Ich glaube, es zu Zyklus obwohl alle möglichen Bitmuster mit einer solchen Einschränkung nicht möglich ist.

Wenn Sie eine n-Bit-Idee, Sie können Zyklus obwohl insgesamt (n + 1) heißt es, bevor ein wenig zu drehen, die Sie bereits gekippt.

Zum Beispiel in einem 3-Bit-Beispiel, wenn Sie mit 111 beginnen, erhalten Sie

111
110
100
000

Und dann sind Sie gezwungen, eine leicht zu schlagen haben Sie bereits einen neuen Zustand zu erhalten blättern.

Answer 4

Basierend auf Ihrem Wecker Beispiel ich nehme an, Sie auf der combiation beenden müssen Sie begonnen, und dass jedes Bit auf dann nur einmal durchlaufen wird ausgeschaltet, z.

  

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

Die Anzahl der Stufen ist die doppelte Anzahl von Bits, so mit 4 Bits Sie die aktuelle Zeit innerhalb eines 3-stündigen Bereichs bekommen.

Answer 5

Sie wollen jedes Bit nur einmal ändern?

Wie:

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

In diesem Fall können Sie einen einfachen Zähler verwenden, wo das Delta von 2 jede Iteration multipliziert (oder verschieben links).

Answer 6

Wenn Gamecat Sie richtig aufgestellt, Ihre Bitmaskenwerte werden:

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

oder unter Verwendung von Verschiebungen:  (1 << i) - 1 für i in 0 ..

Answer 7

„Ich brauche einen Algorithmus in dem der Zustand eines Bits nur einmal ändert sich durch alle Iterationen“

Wenn die obige Aussage wörtlich genommen wird, dann gibt es nur fünf Zustände pro Iteration, wie in anderen Beiträgen erläutert.

Wenn die Frage lautet: „Wie viele mögliche Sequenzen erzeugt werden kann?“, Dann:

Ist der erste Staat immer 0000?

Wenn nicht, dann haben Sie 16 mögliche Anfangszustände.

Ist Ordnung los?

Wenn ja, dann sind Sie 4 haben! = 24 Möglichkeiten, zu wählen, welche ersten Flip-Bits.

So ergibt dies insgesamt 16 * 24 = 384 mögliche Sequenzen, die erzeugt werden können.

Answer 8

Mit Blick auf die ursprüngliche Frage zurück Ich glaube, ich verstehe, was Sie meinen

einfach was ist die kleinste Menge an Bits Sie eine Uhr programmieren können, bezogen auf die Menge der möglichen Bitkombinationen

Die erste Frage ist, wie viele Sequenzen erforderlich sind.

60 Sek x 60 Min x 24 Stunden = 86400 (Kombinationen erforderlich) der nächste Schritt ist, herauszufinden, wie viele Bit mindestens 86.400 Kombinationen zu erzeugen, benötigt

, wenn jemand weiß um die Berechnung

, wie viele Bits 86400 Kombinationen produzieren kann dann ist das deine Antwort. hoffentlich gibt es eine Formel irgendwo online für diese Berechnung

Answer 9

Hier ist ein Beispiel, wie Sie nur ein wenig aus halten können einmal umgedreht werden. Nicht zu wissen, alle Parameter von Ihnen System ist es nicht einfach, ein genaues Beispiel zu geben, aber hier ist man trotzdem.

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

Flipping mit dieser Funktion kann nur ein Flip auf jedes Bit.