11. UVa-11173 Gray Codes/ Gray to Binary and its Reverse version

1. Binary to Gray

문제

<그림1: 문제>

k번째 graycode를 출력하라는 문제임. 사실 n은 안 중요함. (어차피 n bit로 표현할 수 있는 범위를 넘어서는 k를 줄 수 없으니까)

또한 그레이코드의 의의 같은건 별로 안 중요하고 어떻게 만드는지가 중요하니까 밑의 그림을 보자.

<그림2: Binary to Gray converting algorithm>

2진 코드에서 그레이코드 생성하기

1. 최상위비트(MSB)는 그대로 내린다.

2. 이후 어떤 i번째 bit는 i번째 bit와 i+1번쨰 bit를 xor연산한 결과를 쓴다.

 

따라서 2번을 고려하면 그냥 원래의 2진 코드를 오른쪽으로 한번 민 코드와 xor연산 하는것으로 MSB를 제외하고는 다 제대로 연산이 되리라는 것을 생각해볼 수 있다. 그리고 운좋게도 그렇게 하면 MSB도 그냥 원래의 2진코드 것이 내려오는데 MSB가 0과 1일 때로 case를 나눠 생각해보면 알 수 있다. 따라서 코드는 다음과 같다.

 

#include<iostream>
using namespace std;
int main() {
	unsigned int num,N,M;
	cin >> num;
	while (num--) {
		cin >> N >> M;
		cout << (M ^ (M >> 1)) << endl;
	}
	return 0;
}
//11173

N은 받았지만 쓰지도 않는다. 그래도 AC판정이 나오니까 상관 없는듯

 

2. Gray to Binary

문제에서 주어지지는 않았는데 거꾸로도 해보고 싶으니까 해보자.

문제: gray code k가 주어졌을 때 몇번째 gray code인지 구하기.

Binary to Gray는 쉽다. 근데 Gray to Binary는 이렇게 깔끔하게 만들기가 좀 힘들다.

Gray to Binary의 알고리즘은 다음 <그림3>과 같다.

<그림3: Gray to Binary converting algorithm>

MSB는 그대로 내리고 임의의 i번째 bit는 Binary code의 i+1번째 bit와 Gray code의 i번째 bit를 XOR연산해서 만든다. 회로로 표현한 것이 다음 사이트에 있길래 가져온다.

<그림4: Visualization of algorithm>

딱 봐도 한 줄 연산이 안될 것 같다는게 보인다. (optimized 회로가 1-step회로가 아니니까)

그냥 bitset 써서 bit-wise로 for문 돌려야 할 것 같은데? 한 줄 연산은 모르겠다.