La plupart des combinaisons binaires à partir de 4 bits, avec un seul changement par bit

Question

j'ai 4 bits binaires

Bit 3  Bit 2  Bit 1  Bit 0

Normalement, la réponse est simple: 2 ^ 4, soit 16 combinaisons différentes; et cela ressemblerait à quelque chose comme ceci:

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

Cependant, le LSB (bit 0) change d'état à chaque itération.

J'ai besoin d'un algorithme dans lequel l'état d'un bit ne change qu'une fois à travers toutes les itérations. c’est-à-dire que tous mes bits doivent agir comme le MSB (bit 3).

Comment puis-je faire cela?

Modifier

Il semble que la plupart des gens convergent vers 5 solutions possibles. Cependant, cela suppose qu’il existe un point de départ pour la valeur et un point final. Cela n’a pas d’importance alors je vais vous donner un scénario du monde réel à mieux expliquer.

Supposons que j'ai un réveil numérique qui me donne 4 sorties. Chaque sortie peut être programmée pour s’allumer à un certain moment et s’éteindre à un certain moment et est programmée indépendamment les unes des autres, par exemple. Je peux programmer la sortie 1 à 1 heure du matin et éteindre à 3 heures du matin, tandis que je peux programmer la sortie 2 à 19 heures et à 2 heures du matin. Il n'y a aucune restriction quant à la durée pendant laquelle chaque sortie peut rester activée.

Je souhaite maintenant connecter ce réveil à un ordinateur et me rapprocher le plus possible de l'heure actuelle. C'est-à-dire si l'horloge indique qu'il est 14h15, mon ordinateur sait que l'alarme se situe entre 12h et 18h, par exemple. Je veux pouvoir obtenir la plus petite plage possible. Quelle est la plus petite plage possible?

Answer 1

1. Il y a 4 bits.
2. Chaque bit ne peut changer d'état qu'une seule fois.
3. Pour chaque nouvelle valeur, au moins un des bits doit avoir changé d'état par rapport à la valeur précédente.

Par conséquent, vous pouvez avoir au plus 4 changements d'état et au plus 5 valeurs différentes.

Exemple:

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

Modifier:

Très bien, résumons ce que vous voulez dire plutôt que ce que vous dites.

1. Il y a 4 bits.
2. Chaque bit ne peut changer d'état que deux fois . (une fois de 0 à 1 et une fois de 1 à 0)
3. Pour chaque nouvelle valeur, au moins un des bits doit avoir changé d'état par rapport à la valeur précédente.

Par conséquent, vous pouvez avoir au plus 8 changements d'état et au plus 8 valeurs différentes (car le dernier changement d'état ramène nécessairement tous les bits à leur état initial)

Exemple:

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

Ainsi, en réglant les sorties pour: de 3h00 à 15h00, de 6h00 à 18h00, de 9h00 à 21h00 et de midi à minuit, vous pouvez déterminer la période de 3 heures à partir des sorties. Je suggèrerais plutôt de brancher les fils dans la sortie visuelle.

Answer 2

Vous souhaitez un code Gray . Regardez à peu près à mi-chemin pour & "Construire un code gris à n bits &";.

Answer 3

Je pense qu’il est impossible de passer par tous les modèles de bits possibles avec une telle restriction.

Si vous avez une idée de n-bit, vous pouvez parcourir un total de (n + 1) états avant de devoir retourner un peu que vous avez déjà retourné.

Par exemple, dans un exemple à 3 bits, si vous commencez par 111, vous obtenez

111
110
100
000

Ensuite, vous êtes obligé d’en retourner un que vous avez déjà retourné pour obtenir un nouvel état.

Answer 4

Sur la base de votre exemple de réveil, je suppose que vous devez terminer la combinaison que vous avez commencée et que chaque bit peut être activé puis désactivé une seule fois, par exemple.

  

0000 - > 0001 - & Gt; 0011 - & Gt; 0111 - & Gt; 1111   - > 1110 - & Gt; 1100 - & Gt; 1000 - & Gt; 0000

Le nombre d'étapes est le double du nombre de bits. Ainsi, avec 4 bits, vous pouvez obtenir l'heure actuelle dans une plage de 3 heures.

Answer 5

Vous voulez que chaque bit ne change qu'une fois?

J'aime:

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

Dans ce cas, vous pouvez utiliser un simple compteur dans lequel le delta est multiplié par 2 à chaque itération (ou décalage à gauche).

Answer 6

Si Gamecat vous a bien compris, vos valeurs de masque de bits seront:

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

ou, en utilisant des décalages:  (1 & Lt; & Lt; i) - 1 pour i dans 0 ..

Answer 7

& "J'ai besoin d'un algorithme dans lequel l'état d'un bit ne change qu'une fois dans toutes les itérations &";

Si la déclaration ci-dessus est prise à la lettre, il n'y a que cinq états par itération, comme expliqué dans d'autres articles.

Si la question est & "Combien de séquences possibles peuvent être générées? &"; alors:

Le premier état est-il toujours 0000?

Sinon, vous avez 16 états initiaux possibles.

L'ordre est-il important?

Si oui, alors vous en avez 4! = 24 façons possibles de choisir les bits à retourner en premier.

Cela donne donc un total de 16 * 24 = 384 séquences possibles pouvant être générées.

Answer 8

En repensant à la question initiale, je pense comprendre ce que vous voulez dire

simplement quel est le plus petit nombre de bits que vous pouvez utiliser pour programmer une horloge, en fonction du nombre de combinaisons de bits possibles

la première question est de savoir combien de séquences sont nécessaires.

60Secs x 60 minutes x 24 heures = 86400 (combinaisons requises) la prochaine étape consiste à déterminer le nombre de bits requis pour produire au moins 86 400 combinaisons

si quelqu'un connaît le calcul à

combien de bits peuvent produire 86400 combinaisons alors c’est votre réponse. j'espère qu'il y a une formule en ligne quelque part pour ce calcul

Answer 9

Voici un exemple de la manière dont vous pouvez empêcher un élément d’être retourné une seule fois. Ne connaissant pas tous les paramètres de votre système, il n’est pas facile de donner un exemple précis, mais en voici un de toute façon.

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

Le retournement avec cette fonction ne permet qu'un seul retournement par bit.