부동소수점 수

이 문제에서는 컴퓨터에서 실수를 근사적으로 표현하는 방식인 부동소수점 수 형식을 다룬다.

과학적 표기법은 너무 크거나 너무 작아서 보통의 십진 표기로 간결하게 쓸 수 없는 수를 표현할 때 자주 쓰이는 방법이다. 과학적 표기법에서 모든 수는 m × 10e 형태로 쓴다. 여기서 m(가수라고 부른다)은 1 이상 10 미만인 수이고, e(지수라고 부른다)는 정수이다. 예를 들어 13.5는 1.35×101과 같으므로 가수 1.35, 지수 1인 과학적 표기법으로 나타낼 수 있다.

컴퓨터에서는 이진수 표현이 편리하므로, 밑을 10 대신 2로 하는 이진 과학적 표기법을 생각하자. 이진 과학적 표기법에서 모든 수는 m × 2e 형태로 쓴다. 밑이 2이므로 m은 2 미만이라는 제약이 붙는다. 예를 들어 13.5는 1.6875×23과 같으므로 가수 1.6875, 지수 3인 이진 과학적 표기법으로 나타낼 수 있다. 가수 1.6875는 1 + 1/2 + 1/8 + 1/16과 같고, 이는 이진 표기로 1.10112이다. 마찬가지로 지수 3은 이진 표기로 112로 쓸 수 있다.

부동소수점 수는 이진 과학적 표기법으로 나타낸 수를 유한한 비트 수로 표현한다. 가수의 정밀도와 지수의 범위는 비트 수에 따라 제한되지만, 넓은 범위의 수를 어느 정도 높은 정밀도로 표현할 수 있다.

이 문제에서는 실제로 널리 쓰이는 형식을 단순화한 64비트 부동소수점 형식을 다루며, 이 형식으로는 1 이상인 수만 표현할 수 있다. 앞의 12비트는 지수에, 나머지 52비트는 가수에 쓴다. 부동소수점 수의 64비트를 b64...b1이라 하자. e를 부호 없는 이진 정수 (b64...b53)2라 하고, m을 나머지 52비트에 1을 붙인 이진 소수 (1.b52...b1)2라 하면, 이 부동소수점 수는 m × 2e를 나타낸다.

아래는 13.5를 위에서 설명한 형식으로 표현한 비트 열이다.

부동소수점 덧셈 연산에서 결과는 부동소수점 형식으로 표현 가능한 수로 근사해야 한다. 여기서는 근사가 절단에 의해 이루어진다고 가정한다. 두 부동소수점 수 a와 b의 합이 이진 과학적 표기법으로 a + b = m × 2e (1 ≤ m < 2, 0 ≤ e < 212)로 표현될 때, 두 수의 덧셈 연산 결과는 앞의 12비트가 e를 부호 없는 정수로 나타내고 나머지 52비트가 m의 이진 소수점 아래 처음 52비트를 나타내는 부동소수점 수가 된다.

이 근사 방법의 단점은 근사 오차가 쉽게 누적된다는 것이다. 이를 확인하기 위해, 아래 의사 코드처럼 부동소수점 수를 여러 번 더하는 실험을 하자. 여기서 s와 a는 부동소수점 수이고, 각 덧셈의 결과는 위에서 설명한 대로 근사된다.

s := a
for n times {
    s := s + a
}

주어진 부동소수점 수 a와 반복 횟수 n에 대해, 위 의사 코드가 끝났을 때 부동소수점 수 s의 비트를 계산하라.

입력은 최대 1000개의 데이터셋으로 이루어지며, 각 데이터셋은 다음 형식이다.

n
b52...b1

n은 반복 횟수이다. (1 ≤ n ≤ 1018) 각 i에 대해 b**i는 0 또는 1이다. 의사 코드의 부동소수점 수 a는 지수가 0이고 가수가 b52...b1이다.

입력의 끝은 0만 있는 줄로 나타낸다.

각 데이터셋에 대해, 의사 코드가 끝난 뒤의 부동소수점 수 s의 64비트를 0 또는 1인 64자리 숫자의 나열로 한 줄에 출력한다.