비트당 단일 변경이 있는 4비트의 대부분의 이진 조합
-
19-08-2019 - |
문제
4개의 바이너리 비트가 있습니다.
Bit 3 Bit 2 Bit 1 Bit 0
일반적으로 대답은 간단합니다.2^4 또는 16개의 다양한 조합;그러면 다음과 같이 보일 것입니다:
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
그러나 LSB(Bit 0)는 반복할 때마다 상태를 변경합니다.
모든 반복을 통해 비트 상태가 한 번만 변경되는 알고리즘이 필요합니다.즉, MSB(비트 3)처럼 작동하려면 모든 비트가 필요합니다.
어떻게 해야 하나요?
편집하다
대부분의 사람들은 가능한 해결책이 5개밖에 없다고 수렴하고 있는 것 같습니다.그러나 이는 값의 시작점과 끝점이 있다고 가정합니다.이것은 중요하지 않으므로 더 잘 설명하기 위해 실제 시나리오를 제공하겠습니다.
4개의 출력을 제공하는 디지털 알람시계가 있다고 가정해 보겠습니다.각 출력은 특정 시간에 켜지고 특정 시간에 꺼지도록 프로그래밍할 수 있으며 서로 독립적으로 프로그래밍됩니다.출력 1이 오전 1시에 켜지고 오전 3시에 꺼지도록 프로그래밍할 수 있고, 출력 2가 오후 7시에 켜지고 오전 2시에 꺼지도록 프로그래밍할 수 있습니다.각 출력이 켜져 있는 기간에는 제한이 없습니다.
이제 저는 이 알람 시계를 컴퓨터에 연결하고 현재 정확한 시간에 최대한 가까워지길 원합니다.즉, 시계에 시간이 오후 2시 15분이라고 표시되면 내 컴퓨터는 알람이 예를 들어 오후 12시에서 오후 6시 범위 내에 있다는 것을 알고 있습니다.가능한 가장 작은 범위를 얻을 수 있기를 원합니다.내가 얻을 수 있는 가장 작은 범위는 무엇입니까?
해결책
- 4비트가 있습니다.
- 각 비트는 상태를 한 번만 변경할 수 있습니다.
- 각각의 새 값에 대해 비트 중 하나 이상이 이전 값에서 상태가 변경되어야 합니다.
따라서 최대 4개의 상태 변경과 최대 5개의 다른 값을 가질 수 있습니다.
예:
0000 -> 0001 -> 0011 -> 0111 -> 1111
편집하다:
좋습니다. 당신이 말하는 것보다 당신이 의미하는 바를 다시 말해 보겠습니다.
- 4비트가 있습니다.
- 각 비트는 상태만 변경할 수 있습니다. 두 배.(0에서 1까지 한 번, 1에서 0까지 한 번)
- 각각의 새 값에 대해 비트 중 하나 이상이 이전 값에서 상태가 변경되어야 합니다.
따라서 최대 8개의 상태 변경과 최대 8개의 다른 값을 가질 수 있습니다(마지막 상태 변경은 필연적으로 모든 비트를 초기 상태로 되돌리므로).
예:
0000 -> 0001 -> 0011 -> 0111 -> 1111 -> 1110 -> 1100 -> 1000 -> 0000
따라서 출력을 설정하면 다음과 같습니다.오전 3시~오후 3시, 오전 6시~오후 6시, 오전 9시~오후 9시, 정오~자정, 출력에서 3시간 기간을 확인할 수 있습니다.대신 시각적 출력에 전선을 연결하는 것이 좋습니다.
다른 팁
당신은 원합니다 회색 코드. "N 비트 그레이 코드 구성"에 대해서는 절반 정도 내려다보십시오.
나는 그러한 제한으로 가능한 모든 비트 패턴이지만 순환하는 것이 불가능하다고 생각합니다.
N- 비트 아이디어가있는 경우, 이미 뒤집힌 부분을 뒤집기 전에 총 (n+1) 상태를 통해 순환 할 수 있습니다.
예를 들어, 3 비트 예에서는 111로 시작하면
111
110
100
000
그리고 당신은 이미 새로운 상태를 얻기 위해 뒤집은 것을 뒤집어야합니다.
알람 시계 예제를 기반으로 시작한 조합을 마무리해야한다고 가정하고 각 비트를 한 번만 순환 할 수 있다고 가정합니다.
0000 -> 0001 -> 0011 -> 0111 -> 1111 -> 1110 -> 1100 -> 1000 -> 0000
단계의 수는 비트 수의 두 배이므로 4 비트로 현재 시간을 3 시간 범위 내에 얻을 수 있습니다.
각 비트가 한 번만 변경되기를 원하십니까?
처럼:
0000 -> 0001 -> 0011 -> 0111 -> 1111
이 경우 델타에 각 반복 (또는 왼쪽으로 이동)을 곱한 간단한 카운터를 사용할 수 있습니다.
Gamecat이 올바르게 얻은 경우 비트 마스크 값이 다음과 같습니다.
1 - 1
2 - 1
4 - 1
8 - 1
16 - 1
etc.
2^i - 1
또는 교대 근무 사용 : (1 << i) -1의 경우 1 ..
"비트 상태가 모든 반복을 통해 한 번만 변경되는 알고리즘이 필요합니다."
위의 진술이 문자 그대로 취해지면 다른 게시물에서 설명한 것처럼 반복 당 5 개의 상태 만 있습니다.
질문이 "얼마나 많은 가능한 시퀀스를 생성 할 수 있습니까?"라면 :
첫 번째 상태는 항상 0000입니까?
그렇지 않다면 16 개의 가능한 초기 상태가 있습니다.
주문이 중요합니까?
그렇다면, 당신은 4가 있습니다! = 24 먼저 뒤집을 비트를 선택할 수있는 가능한 방법.
따라서 이것은 총 16*24 = 384 가능한 시퀀스를 생성 할 수 있습니다.
원래 질문을 다시 보면 무슨 뜻인지 이해한 것 같습니다.
가능한 비트 조합의 양을 기준으로 시계를 프로그래밍하는 데 사용할 수 있는 가장 작은 비트 양은 무엇입니까?
첫 번째 질문은 얼마나 많은 시퀀스가 필요한지입니다.
60 초 x 60 분 x 24hrs = 86400 (조합 필요) 다음 단계는 86400 개 이상의 조합을 생산하는 데 필요한 비트 수를 해결하는 것입니다.
누군가가 계산을 알고 있다면
86400개의 조합을 생성할 수 있는 비트 수는 얼마입니까? 그게 답입니다.이 계산을 위한 공식이 온라인 어딘가에 있기를 바랍니다.
다음은 한 번만 뒤집는 것을 막을 수있는 방법에 대한 예입니다. 시스템의 모든 매개 변수를 알지 못하는 것은 정확한 예를 제시하기가 쉽지 않지만 여기에 하나가 있습니다.
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;
}
}
이 함수를 뒤집으면 각 비트에서 하나의 뒤집기 만 허용됩니다.