비트 반전 (쉬움)

과학자가 되고 싶은 클레오파시는 최근 새 프로세서를 개발했다. 이 프로세서에는 A부터 Z까지 이름이 붙은 26개의 레지스터가 있다. 각 레지스터는 8비트 부호 없는 정수를 저장하는 변수다.

이 새 프로세서는 대단히 단순하다. 아래 표에 나온 명령어만 지원한다. (모든 명령어에서 R은 레지스터 이름, C는 상수, X는 레지스터 이름 또는 상수다. 모든 상수는 8비트 부호 없는 정수, 즉 0부터 255까지의 수다.)

참고:

• not을 제외한 모든 명령어에서 두 번째 인자가 레지스터 이름이면, 그 레지스터의 내용은 변하지 않는다.
• shl이나 shr이 호출되면, 첫 번째 인자의 값을 시프트한 결과는 한쪽 끝이 잘리고 다른 쪽 끝이 0으로 채워진다. 예를 들어 X가 이진수 10110110이면 X shr 2는 00101101이다.

예시 작업

입력에 임의의 8비트 부호 없는 정수 a와 b가 들어 있다고 하자. 이 수를 읽고, a = b일 때에만 z = 0이 되는 정수 z를 출력하는 프로그램을 작성하라. (즉 a와 b가 다르면 z는 양수여야 한다.)

문제 명세

각 데이터 세트마다, 클레오파시의 프로세서에서 다음 작업을 해결하는 프로그램을 작성해야 한다. 프로그램의 입력은 정수들의 수열이고, 각 정수는 0 또는 1이다. 프로그램의 출력은 그 수열의 각 원소를 순서대로 부정한 수열이어야 한다. (즉 각 0을 1로, 각 1을 0으로 바꾼다.)

수열의 길이는 정확히 7이다. 프로그램에서 not 명령어는 많아야 한 번만 사용할 수 있다. 프로그램은 명령어를 100개 이하로 포함해야 한다.

get과 put 명령어는 각각 정확히 7번 사용해야 한다.

이 문제에는 입력이 없다.

프로그램을 일반 ASCII 텍스트로 제출하라. 텍스트의 각 줄에는 완전한 명령어 하나가 들어 있거나 공백만 있을 수 있다. 올바른 프로그램이 아닌 것을 제출하면 “Wrong answer”로 판정되고 그에 맞는 오류 메시지를 받는다.

가능한 풀이는 여러 가지다. 우리 풀이에서는 입력을 레지스터 A와 B로 읽고, 두 값의 비트 단위 xor을 레지스터 Z에 계산해 출력한다.

하지만 xor 명령어는 없다. and, or, not을 조합해 만들어야 한다. 먼저 (not-A and B)를 C에, (not-B and A)를 D에 만든다. 마지막으로 (C or D)를 Z에 저장하면 끝이다.

왜 이렇게 되는가? 두 수가 같으면 C와 D가 모두 0이므로 Z도 0이다. 두 수가 다르면, 두 수의 이진 표현이 다른 어떤 자릿수 d를 생각하자. 이 자릿수가 A에서 0이면 B에서는 1이어야 한다. 그러면 C에서 1이고 따라서 Z에서도 1이다. 이 자릿수가 A에서 1이면 B에서는 0이어야 하고, D에서 1, Z에서 1이다.