Tengo 4 bits binarios

Bit 3  Bit 2  Bit 1  Bit 0

Normalmente la respuesta es simple: 2^4, o de 16 diferentes combinaciones; y sería parecido al 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 sólo cambia una vez a través de todas las iteraciones; i.e, necesito de toda mi 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 para no ser sólo 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 ejemplo del mundo real para explicar mejor.

Supongamos que tengo un reloj despertador digital que me da 4 salidas. Cada salida puede ser programado para activarse en un momento determinado y en un tiempo determinado y son programados independientes el uno del otro, por ejemplo. Me puede programar la salida 1 para ir a la 1 am y se apague a las 3 de la mañana, mientras yo puede programar la salida de 2 a 7 pm y hasta las 2 de la mañana. No hay restricciones a la duración de cada salida puede permanecer en.

Ahora quiero enganchar el reloj de alarma a un equipo y llegar lo más cerca posible a la actual hora correcta. yo.e Si el reloj dice que el tiempo es de 2:15 pm, mi equipo sabe que la alarma está dentro de las 12 pm a 6 pm gama, por ejemplo. Quiero ser capaz de obtener el menor intervalo posible. Cuál es el menor intervalo posible que yo pueda conseguir?

  • Este es un problema interesante. Estoy tratando de averiguar ahora, me gustan los retos. = ) ¿Sabe usted si es posible, o es que es una prueba/refutar?
  • Bits normalmente están numeradas de manera que LSB es el bit 0, me dejó editar eso para usted. 🙂
  • He venido para arriba con una solución, pero no del estado en la pregunta porque quiero ver lo que otras personas han llegado con. La verdad es que tengo uso de este en algunos de interconexión del ordenador.
  • ¿El equipo tiene su propio reloj interno? Si es así, no sabe qué hora es, y no necesita de la alarma del reloj. Si no, entonces ¿cómo 4 bits de la alarma del reloj dan a la computadora de cualquier información sobre el tiempo?
  • También, usted declaró en un principio que cada bit puede cambiar sólo una vez, pero en su «reloj» ejemplo, cada bit cambia dos veces. Por ejemplo, originalmente off, on a la 1 de la madrugada, fuera de nuevo a las 3 de la madrugada.
  • No importa, creo que entiendo lo que quieres decir ahora: * Una persona establece un reloj despertador digital para hacer 4 bits individualmente encender una vez durante el día, y luego se apagará una vez (durante el mismo día, o se puede activar a las 11 de la noche y se apague a la 1 de la madrugada)? (continuación)
  • * Si la persona no sabe qué hora es, pero las miradas en el estado de los bits, que debe ser capaz de deducir que el momento actual está dentro de un cierto rango. * La pregunta que se plantea es: ¿Cuál debería ser la hora de encendido / hora de apagado para cada uno de los bits que produciría el min(max(deducible intervalo de tiempo))?

InformationsquelleAutor darudude | 2009-01-16

9 Comentarios

  1. 12
    1. Hay 4 bits.
    2. Cada bit puede cambiar el estado sólo una vez.
    3. Para cada nuevo valor, al menos uno de los bits que debe de haber cambiado el estado a partir del valor anterior.

    Por lo tanto, puede tener en la mayoría de los 4 cambios de estado, y en la mayoría de los 5 valores diferentes.

    Ejemplo:

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

    Edición:

    Muy bien, vamos a repetir de lo que significa, más que por lo que dices.

    1. Hay 4 bits.
    2. Cada bit puede cambiar el estado sólo 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 que debe de haber cambiado el estado a partir del valor anterior.

    Por lo tanto, usted puede tener un máximo de 8 cambios de estado, y en la mayoría de los 8 valores diferentes (desde el último cambio de estado trae necesariamente todos los bits de vuelta a su estado inicial)

    Ejemplo:

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

    Así, mediante la configuración de las salidas: 3 AM – 3 PM, 6 AM – 6 PM, 9 AM – 9 PM y el mediodía hasta la medianoche, se puede determinar qué periodo de 3 horas es de las salidas. Te sugiero que conectar los cables en la salida visual en su lugar.

    • Por favor, busque en el Código Gray, como Jon Skeet sugiere.
    • bingo! esto es lo que me emant. Tengo 8 combinaciones así, tenía la esperanza de que podría conseguir mejor.
  2. 7

    Desea un Código Gray. Mirar alrededor de la mitad hacia abajo para «la Construcción de un n-bit del código gray».

    • No, porque incluso en el Código Gray, el LSB cambia dos veces. No tres veces, pero todavía más de una vez.
    • Sí, había leído mal la pregunta – pero «sólo cambiar cada poco una vez» es una muy tonta restricción con una solución trivial.
  3. 3

    Creo que es imposible ciclo pesar de todos los posibles patrones de bits con una restricción de este tipo.

    Si usted tiene un n-bits idea, puede ciclar un total de (n+1) estados antes de tener que voltear un poco ya has volteado.

    Por ejemplo, en una de 3 bits ejemplo, si usted comienza con 111, consigue

    111
    110
    100
    000
    

    Y, a continuación, usted está obligado a voltear uno ya has volteado a obtener un nuevo estado.

  4. 1

    Basado en el ejemplo del reloj con alarma asumo que usted necesita para terminar en el combiation en el que comenzó, y que cada bit puede ser activa, a continuación, sólo una vez, por ejemplo,

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

    El número de pasos es dos veces el número de bits, por lo que con 4 bits se puede obtener la hora actual para dentro de 3 horas de intervalo.

    • Te juro que no lea esto antes de editar mi respuesta.
  5. 0

    Desea que cada granito de arena para cambiar sólo una vez?

    Como:

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

    En ese caso, usted puede utilizar un simple mostrador donde el delta se multiplica por 2 cada iteración (o mayús izquierda).

  6. 0

    Si Gamecat tengo correctamente,
    su máscara de bits de los valores serán:

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

    o bien, con los cambios:
    (1 << i) – 1 for i in 0..

  7. 0

    «Necesito un algoritmo donde el estado de un bit sólo cambia una vez a través de todas las iteraciones»

    Si la instrucción anterior es tomado literalmente, entonces hay sólo cinco estados por iteración, como se ha explicado en otros posts.

    Si la pregunta es «¿cuántos posibles secuencias se pueden generar?», entonces:

    Es el primer estado siempre 0000?

    Si no, entonces usted tiene 16 posibles estados iniciales.

    ¿ El fin de la materia?

    Si sí, entonces usted tiene 4! = 24 maneras posibles para que elija el que los bits para voltear primero.

    Así, esto da un total de 16*24 = 384 posibles secuencias que pueden ser generados.

    • Sí quiero decir que el método literal
  8. 0

    Mirar 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 utilizar para programar un reloj, basado en la cantidad de posibles combinaciones de bits

    la primera pregunta es cómo muchas secuencias son necesarios.

    60 segundos x 60 Minutos x 24 horas = 86400 (combinaciones necesario)
    el siguiente paso es averiguar a cuántos bits son necesarios para producir al menos 86400 combinaciones

    si alguien lo sabe el cálculo para

    cuántos bits puede producir 86400 combinaciones entonces esa es su respuesta.
    esperemos que haya una fórmula en línea en algún lugar para este cálculo

  9. 0

    Aquí es un ejemplo de cómo se puede mantener un poco de sólo ser volteado de una vez. No sabiendo que todos los parámetros del sistema no es fácil dar un fiel ejemplo pero aquí es 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 sólo permitirá un flip en cada uno de los bits.

Dejar respuesta

Please enter your comment!
Please enter your name here