그레이 코드

이진수는 밑이 $2$인 수이고, 각 자리(비트)의 자릿값은 $2$의 거듭제곱이다. 예를 들어 십진수 $23$은 이진수로 $10111$인데, 다음이 성립하기 때문이다.

$(1 \times 2^4) + (0 \times 2^3) + (1 \times 2^2) + (1 \times 2^1) + (1 \times 2^0) = 16 + 4 + 2 + 1 = 23$

그레이 코드 수열은 이진값을 나열한 것으로, 각 값이 바로 앞 값과 정확히 한 비트만 다르다. 아래 표는 3비트 이진수의 표준 그레이 코드 수열이다.

이진수를 대응하는 표준 그레이 코드 값으로 바꾸는 방법은 아주 간단하다. 이진값 $011$을 바꾼다고 하자. 먼저 첫 비트를 그대로 옮겨 적는다.

0 1 1
v
0

둘째 비트는 주어진 이진수의 첫째 비트와 둘째 비트를 더해서 얻는다. 합은 $0 + 1 = 1$이다.

0 + 1 1
    v
0   1

셋째 비트는 주어진 이진수의 둘째 비트와 셋째 비트를 더해서 얻는다. 합은 이진수로 $1 + 1 = 10$이지만 올림은 버리므로 오른쪽 끝 비트인 $0$만 취한다.

0 1 + 1
      v
0 1   0

따라서 답은 $010$이다.

일반적으로 첫 비트를 빼면, 표준 그레이 코드의 $k$번째 비트는 주어진 이진수의 $k-1$번째 비트와 $k$번째 비트를 더한 뒤 올림을 버려서 얻는다. 올림을 버리는 덧셈은 다음 네 가지가 전부다.

  0    0    1    1
+ 0  + 1  + 0  + 1
---  ---  ---  ---
  0    1    1    0

$n$비트 이진값을 대응하는 $n$비트 표준 그레이 코드 값으로 바꾸는 프로그램을 작성하시오. $1 \le n \le 20$이다.

입력은 두 줄이다.

1. 첫째 줄에 비트 수 $n$이 주어진다. $1 \le n \le 20$이다.
2. 둘째 줄에 $n$비트 이진수를 나타내는, 길이가 $n$인 비트 문자열이 주어진다.

주어진 $n$비트 이진수에 대응하는 표준 그레이 코드를 길이 $n$인 비트 문자열로 출력한다.