La maggior parte delle combinazioni binarie da 4 bit, con singola modifica per bit

Question

Ho 4 bit binari

Bit 3  Bit 2  Bit 1  Bit 0

Normalmente la risposta è semplice: 2 ^ 4 o 16 combinazioni diverse; e sarebbe simile al seguente:

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

Tuttavia, LSB (Bit 0) cambia stato ogni iterazione.

Ho bisogno di un algoritmo in cui lo stato di un bit cambia solo una volta attraverso tutte le iterazioni; cioè, ho bisogno di tutti i miei bit per agire come MSB (Bit 3).

Come posso farlo?

Modifica

Sembra che la maggior parte delle persone stia convergendo in quanto esistono solo 5 possibili soluzioni. Tuttavia, ciò presuppone che ci sia un punto iniziale per il valore e un punto finale. Non importa, quindi ho intenzione di dare uno scenario del mondo reale per spiegare meglio.

Supponiamo che io abbia una sveglia digitale che mi dà 4 uscite. Ogni uscita può essere programmata per accendersi ad un certo orario e spegnersi ad un certo momento e sono programmate indipendentemente l'una dall'altra, ad es. Posso programmare l'uscita 1 per attivarsi all'1 del mattino e spegnersi alle 3 del mattino, mentre posso programmare l'uscita 2 per attivarsi alle 7 di sera e spegnere alle 2 del mattino. Non ci sono limiti alla durata di permanenza di ogni uscita.

Ora voglio collegare questa sveglia a un computer e avvicinarmi il più possibile all'ora esatta corrente. vale a dire se l'orologio indica che sono le 14:15, il mio computer sa che la sveglia è compresa tra le 12:00 e le 18:00. Voglio essere in grado di ottenere la gamma più piccola possibile. Qual è la gamma più piccola possibile che posso ottenere?

Answer 1

1. Ci sono 4 bit.
2. Ogni bit può cambiare stato una sola volta.
3. Per ogni nuovo valore, almeno uno dei bit deve aver cambiato stato rispetto al valore precedente.

Pertanto, puoi avere al massimo 4 cambi di stato e al massimo 5 valori diversi.

Esempio:

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

Modifica

Molto bene, riaffermiamo da ciò che intendi piuttosto che da ciò che dici.

1. Ci sono 4 bit.
2. Ogni bit può cambiare stato solo due volte . (una volta da 0 a 1 e una volta da 1 a 0)
3. Per ogni nuovo valore, almeno uno dei bit deve aver cambiato stato rispetto al valore precedente.

Pertanto, è possibile avere al massimo 8 cambi di stato e al massimo 8 valori diversi (poiché l'ultimo cambio di stato riporta necessariamente tutti i bit al loro stato iniziale)

Esempio:

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

Quindi, impostando le uscite per: 3: 00-15: 00, 6: 00-18: 00, 9: 00-21: 00 e mezzogiorno-mezzanotte, è possibile determinare il periodo di 3 ore dalle uscite. Suggerirei invece di collegare i fili all'output visivo.

Answer 2

Desideri un Codice grigio . Cerca a metà circa & Quot; Costruzione di un codice gray n-bit & Quot ;.

Answer 3

Credo che sia impossibile passare in rassegna tutti i possibili schemi di bit con tale limitazione.

Se hai un'idea di n-bit, puoi scorrere tra un totale di (n + 1) stati prima di dover capovolgere un po 'che hai già capovolto.

Ad esempio, in un esempio a 3 bit, se inizi con 111, ottieni

111
110
100
000

E poi sei costretto a capovolgerne uno che hai già capovolto per ottenere un nuovo stato.

Answer 4

In base al tuo esempio di sveglia, suppongo che tu debba finire sulla combinazione che hai iniziato e che ogni bit può essere attivato e disattivato una sola volta, ad es.

  

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

Il numero di passaggi è il doppio del numero di bit, quindi con 4 bit è possibile ottenere l'ora corrente entro un intervallo di 3 ore.

Answer 5

Vuoi che ogni bit cambi una sola volta?

Come:

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

In quel caso puoi usare un semplice contatore in cui il delta viene moltiplicato per 2 per ogni iterazione (o spostamento a sinistra).

Answer 6

Se Gamecat ti ha preso correttamente, i valori della maschera di bit saranno:

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

oppure, usando i turni:  (1 & Lt; & Lt; i) - 1 per i in 0 ..

Answer 7

" Ho bisogno di un algoritmo in cui lo stato di un bit cambia solo una volta attraverso tutte le iterazioni "

Se la dichiarazione sopra è presa alla lettera, allora ci sono solo cinque stati per iterazione, come spiegato in altri post.

Se la domanda è " Quante possibili sequenze possono essere generate? " ;, quindi:

Il primo stato è sempre 0000?

In caso contrario, hai 16 possibili stati iniziali.

L'ordine è importante?

Se sì, allora hai 4! = 24 possibili modi per scegliere quali bit lanciare per primi.

Quindi, questo dà un totale di 16 * 24 = 384 possibili sequenze che possono essere generate.

Answer 8

Guardando indietro alla domanda originale, penso di capire cosa intendi

qual è la quantità minima di bit che puoi usare per programmare un orologio, in base alla quantità di possibili combinazioni di bit

la prima domanda è quante sequenze sono necessarie.

60 secondi x 60 minuti x 24 ore = 86400 (combinazioni richieste) il prossimo passo è capire quanti bit sono necessari per produrre almeno 86400 combinazioni

se qualcuno conosce il calcolo per

quanti bit possono produrre 86400 combinazioni, questa è la tua risposta. speriamo che ci sia una formula online da qualche parte per questo calcolo

Answer 9

Ecco un esempio di come puoi evitare che un po 'venga capovolto solo una volta. Non conoscendo tutti i parametri del tuo sistema non è facile dare un esempio accurato ma eccone comunque uno

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

Lanciando con questa funzione si consentirà un solo capovolgimento su ciascun bit.