비트당 단일 변경이 있는 4비트의 대부분의 이진 조합

StackOverflow https://stackoverflow.com/questions/450617

문제

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시 범위 내에 있다는 것을 알고 있습니다.가능한 가장 작은 범위를 얻을 수 있기를 원합니다.내가 얻을 수 있는 가장 작은 범위는 무엇입니까?

도움이 되었습니까?

해결책

  1. 4비트가 있습니다.
  2. 각 비트는 상태를 한 번만 변경할 수 있습니다.
  3. 각각의 새 값에 대해 비트 중 하나 이상이 이전 값에서 상태가 변경되어야 합니다.

따라서 최대 4개의 상태 변경과 최대 5개의 다른 값을 가질 수 있습니다.

예:

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

편집하다:

좋습니다. 당신이 말하는 것보다 당신이 의미하는 바를 다시 말해 보겠습니다.

  1. 4비트가 있습니다.
  2. 각 비트는 상태만 변경할 수 있습니다. 두 배.(0에서 1까지 한 번, 1에서 0까지 한 번)
  3. 각각의 새 값에 대해 비트 중 하나 이상이 이전 값에서 상태가 변경되어야 합니다.

따라서 최대 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;
    }
}

이 함수를 뒤집으면 각 비트에서 하나의 뒤집기 만 허용됩니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top