La mayoría de las combinaciones binarias de 4 bits, con un solo cambio por bit

Question

Tengo 4 bits binarios

Bit 3  Bit 2  Bit 1  Bit 0

Normalmente la respuesta es simple: 2 ^ 4, o 16 combinaciones diferentes; y se parecería a lo siguiente:

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

Sin embargo, el LSB (Bit 0) cambia de estado cada iteración.

Necesito un algoritmo donde el estado de un bit solo cambie una vez a través de todas las iteraciones; es decir, necesito todos mis bits para actuar como el MSB (Bit 3).

¿Cómo puedo hacer esto?

Editar

Parece que la mayoría de las personas están convergiendo en que solo hay 5 posibles soluciones. Sin embargo, esto supone que hay un punto de partida para el valor y un punto final. Esto no importa, así que voy a dar un escenario del mundo real para explicarlo mejor.

Supongamos que tengo un reloj despertador digital que me da 4 salidas. Cada salida se puede programar para que se encienda en un momento determinado y se apague en un momento determinado y se programan de forma independiente entre sí, por ejemplo. Puedo programar la salida 1 para que se active a la 1 a.m. y se apague a las 3 a.m., mientras que puedo programar la salida 2 para que se active a las 7 p.m. y se apague a las 2 a.m. No hay restricciones en cuanto a la duración de cada salida.

Ahora quiero conectar este despertador a una computadora y acercarme lo más posible a la hora correcta actual. es decir, si el reloj indica que son las 2:15 p.m., mi computadora sabe que la alarma está dentro del rango de 12 p.m. a 6 p.m., por ejemplo. Quiero poder obtener el rango más pequeño posible. ¿Cuál es el rango más pequeño posible que puedo obtener?

Answer 1

1. Hay 4 bits.
2. Cada bit puede cambiar de estado solo una vez.
3. Para cada nuevo valor, al menos uno de los bits debe haber cambiado el estado del valor anterior.

Por lo tanto, puede tener como máximo 4 cambios de estado y como máximo 5 valores diferentes.

Ejemplo:

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

Edición :

Muy bien, reformulemos lo que quieres decir en lugar de lo que dices.

1. Hay 4 bits.
2. Cada bit puede cambiar de estado solo dos veces . (una vez de 0 a 1 y una vez de 1 a 0)
3. Para cada nuevo valor, al menos uno de los bits debe haber cambiado el estado del valor anterior.

Por lo tanto, puede tener como máximo 8 cambios de estado y como máximo 8 valores diferentes (dado que el último cambio de estado necesariamente trae todos los bits a su estado inicial)

Ejemplo:

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

Entonces, al configurar las salidas para: 3 AM - 3 PM, 6 AM - 6 PM, 9 AM - 9 PM y mediodía - medianoche, puede determinar qué período de 3 horas es de las salidas. Sugeriría enchufar cables en la salida visual en su lugar.

Answer 2

Desea un Código gris . Mire a la mitad de & Quot; Construyendo un código gris de n bits & Quot ;.

Answer 3

Creo que es imposible realizar un ciclo a través de todos los patrones de bits posibles con dicha restricción.

Si tiene una idea de n bits, puede realizar un ciclo a través de un total de (n + 1) estados antes de tener que cambiar un bit que ya ha cambiado.

Por ejemplo, en un ejemplo de 3 bits, si comienzas con 111, obtienes

111
110
100
000

Y luego te ves obligado a voltear uno que ya volteaste para obtener un nuevo estado.

Answer 4

Basado en el ejemplo de su reloj de alarma, supongo que necesita finalizar la combinación en la que comenzó, y que cada bit puede activarse y desactivarse solo una vez, por ejemplo

  

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

El número de pasos es el doble del número de bits, por lo que con 4 bits puede obtener la hora actual dentro de un rango de 3 horas.

Answer 5

¿Desea que cada bit cambie solo una vez?

Me gusta:

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

En ese caso, puede usar un contador simple donde el delta se multiplica por 2 en cada iteración (o desplazamiento hacia la izquierda).

Answer 6

Si Gamecat te consiguió correctamente, sus valores de máscara de bits serán:

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

o, usando turnos:  (1 & Lt; & Lt; i) - 1 para i en 0 ..

Answer 7

" Necesito un algoritmo donde el estado de un bit solo cambie una vez a través de todas las iteraciones "

Si la declaración anterior se toma literalmente, entonces solo hay cinco estados por iteración, como se explica en otras publicaciones.

Si la pregunta es " ¿Cuántas secuencias posibles se pueden generar? " ;, entonces:

¿El primer estado siempre es 0000?

Si no, entonces tiene 16 estados iniciales posibles.

¿Importa el orden?

Si es así, ¡entonces tienes 4! = 24 posibles formas de elegir qué bits voltear primero.

Entonces, esto da un total de 16 * 24 = 384 secuencias posibles que se pueden generar.

Answer 8

Mirando hacia atrás a la pregunta original, creo que entiendo lo que quieres decir

simplemente cuál es la menor cantidad de bits que puede usar para programar un reloj, en función de la cantidad de combinaciones de bits posibles

la primera pregunta es cuántas secuencias se requieren.

60 segundos x 60 minutos x 24 horas = 86400 (se requieren combinaciones) el siguiente paso es calcular cuántos bits se requieren para producir al menos 86400 combinaciones

si alguien conoce el cálculo para

cuántos bits pueden producir 86400 combinaciones, entonces esa es tu respuesta. ojalá haya una fórmula en línea en algún lugar para este cálculo

Answer 9

Aquí hay un ejemplo de cómo puedes evitar que un poco solo se voltee una vez. Sin conocer todos los parámetros de su sistema, no es fácil dar un ejemplo exacto, pero aquí hay uno de todos modos.

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

Voltear con esta función solo permitirá un volteo en cada bit.