A maioria das combinações binárias de 4 bits, com variação único por pouco

Question

Eu tenho 4 bits binários

Bit 3  Bit 2  Bit 1  Bit 0

Normalmente a resposta é simples: 2 ^ 4, ou 16 combinações diferentes; e que seria parecido com o seguinte:

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

No entanto, a LSB (Bit 0) muda de estado a cada iteração.

Eu preciso de um algoritmo onde o estado de um bit só muda uma vez por todas as iterações; ou seja, eu preciso de todos os meus bits para agir como o MSB (Bit 3).

Como posso fazer isso?

Editar

Parece que a maioria das pessoas estão convergindo para a existência de apenas 5 soluções possíveis. No entanto, esta assume que há um ponto de partida para o valor e um ponto final. Isso não importa, então eu vou dar um mundo real cenário para explicar melhor.

Suponha que eu tenho um despertador digital que me dá 4 saídas. Cada saída pode ser programado para ir em um determinado momento e desligar em um determinado momento e são programados independentes um do outro, por exemplo. I pode programar a saída 1 para ir à 1 da manhã e desligar às 3 da manhã, enquanto eu pode programar a saída 2 para ir às 7 pm e off às 2 da manhã. Não há restrições para quanto tempo cada saída pode ficar.

Agora eu quero ligar este despertador para um computador e chegar o mais próximo possível da hora correta atual. i Se o relógio diz que o tempo é 02:15, o meu computador sabe que o alarme está dentro do intervalo de doze horas - seis horas, por exemplo. Eu quero ser capaz de obter o menor número possível. Qual é o menor número possível eu posso conseguir?

Answer 1

1. Existem 4 bits.
2. Cada bit pode alterar o estado apenas uma vez.
3. Para cada novo valor, pelo menos um dos bits deve ter mudado de estado a partir do valor anterior.

Portanto, você pode ter no máximo 4 alterações de estado e, no máximo, 5 valores diferentes.

Exemplo:

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

Editar:

Muito bem, vamos reafirmar a partir do que você quer dizer em vez do que você diz.

1. Existem 4 bits.
2. Cada bit pode alterar o estado única duas vezes . (Uma vez 0-1, e uma vez 1-0)
3. Para cada novo valor, pelo menos um dos bits deve ter mudado de estado a partir do valor anterior.

Portanto, você pode ter no máximo 8 alterações de estado e no máximo 8 valores diferentes (desde a última mudança de estado necessariamente traz todos os bits volta ao seu estado inicial)

Exemplo:

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

Assim, definindo as saídas para: 03:00-03:00, seis horas - seis horas, nove horas - nove horas e meio-dia - meia-noite, você pode determinar qual período de 3 horas é a partir das saídas. Eu sugiro ligar fios na saída visual vez.

Answer 2

Você quer um href="http://en.wikipedia.org/wiki/Gray_code" rel="nofollow noreferrer"> código Gray . Olhada na metade de "Construindo um código de cinza n-bit".

Answer 3

Eu acredito que é impossível ciclo embora todos os padrões de bits possíveis com essa restrição a.

Se você tem uma idéia n-bit, você pode dar um ciclo embora um total de (n + 1) estados antes de ter que virar um pouco que você já jogou.

Por exemplo, em um exemplo 3-bit, se você começar com 111, você recebe

111
110
100
000

E, em seguida, você é forçado a virar um você já virou para obter um novo estado.

Answer 4

Com base no seu exemplo despertador Eu suponho que você precisa para terminar na combiation você começou, e que cada bit pode ser repetido então fora apenas uma vez, por exemplo.

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

O número de passos é o dobro do número de bits, então com 4 bits que você poderia obter o tempo atual para dentro de um intervalo de 3 horas.

Answer 5

Você quer que cada bit de mudar apenas uma vez?

Como:

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

Nesse caso, você pode usar um contador simples, onde o delta é multiplicado por 2 cada iteração (ou deslocamento para a esquerda).

Answer 6

Se Gamecat tenho você corretamente, seus valores de bitmask será:

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

ou, usando turnos: (1 << i) - 1 para i em 0 ..

Answer 7

"Eu preciso de um algoritmo onde o estado de um bit só muda uma vez por todas as iterações"

Se a afirmação acima é tomado literalmente, então há apenas cinco estados por iteração, conforme explicado em outros lugares.

Se a questão é, então, "Quantas seqüências possíveis pode ser gerado?":

É o primeiro estado sempre 0000?

Se não, então você tem 16 possíveis estados iniciais.

IMPORTA ordem?

Se sim, então você tem 4! = 24 maneiras possíveis para escolher quais bits para virar primeiro.

Portanto, isto dá um total de 16 * 24 = 384 possíveis sequências que podem ser gerados.

Answer 8

Olhando para trás, a pergunta original Eu acho que entendo o que quer dizer

simplesmente o que é a menor quantidade de bits que você pode usar para programar um relógio, com base na quantidade de combinações possíveis de bits

a primeira questão é como muitas seqüências são necessários.

60Secs x 60 min x 24 horas = 86400 (combinações necessário) o próximo passo é descobrir quantos bits são necessários para produzir, pelo menos, 86400 combinações

se alguém sabe o cálculo para

quantos bits pode produzir 86400 combinações então isso é a sua resposta. espero que não existe uma fórmula on-line em algum lugar para este cálculo

Answer 9

Aqui está um exemplo de como você pode manter um pouco a partir de apenas sendo capotou uma vez. Sem saber todos os parâmetros de seu sistema não é fácil dar um exemplo preciso, mas aqui é um de qualquer maneira.

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

Lançando com esta função só irá permitir uma aleta em cada bit.