A maioria das combinações binárias de 4 bits, com variação único por pouco
-
19-08-2019 - |
Pergunta
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?
Solução
- Existem 4 bits.
- Cada bit pode alterar o estado apenas uma vez.
- 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.
- Existem 4 bits.
- Cada bit pode alterar o estado única duas vezes . (Uma vez 0-1, e uma vez 1-0)
- 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.
Outras dicas
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".
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.
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.
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).
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 ..
"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.
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
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.