Hendrie Sequence 
The Hendrie Sequence ``H"is a self-describing sequence defined as follows:

H(1) = 0

If we expand every number x in H to a subsequence containing x 0's followed by the number x + 1, the resulting sequence is still H (without its first element).

Thus, the first few elements of H are:
0,1,0,2,1,0,0,3,0,2,1,1,0,0,0,4,1,0,0,3,0,...
You must write a program that, given n, calculates the nth element of H.

Input 

Each test case consists of a single line containing the integer 
n
 (
 
0 < n < 263
) . Input is terminated with a line containing the number ` 0
' which of course should not be processed.

Output 

For each test case, output the 
n
th element of H on a single line.

Sample Input 

4
7
44
806856837013209088
0

Sample Output 

2
0
3
16

제목: Hendrie 서열 n항이 얼마인지 구하세요.
사고방식: 앞의 몇 가지 서열을 작성하면
0 1 02 1003 02110004 1003020211100005.....
법칙을 발견하여 1,2,4,8을 길이로 경계를 나누고 각 줄은 i-2줄, i-3줄, i-4줄...마지막 끝에 i를 추가합니다.이 법칙이 있으면 차례로 해답을 구할 수 있다. n은 현재 필요한 길이를 나타낸 다음에 2*m로 n보다 적지 않은 숫자를 찾아낸다. 만약에 같다면 마침 찾았다는 뜻이다. 만약에 크면 뒤에서 앞으로 생각하고 먼저 0과 1의 상황을 다 고려해야 한다.만약 아직 만족하지 않는다면, 길이가 2 이상인 열을 계속 고려하고, 작은 것을 찾으면 이 상황 안에 있고, 나머지 길이는 2 * 길이-n이다.차례로 해답을 구하다.
이 문제는 매우 비참하게 구덩이가 되었군요. 주로 문제 n의 범위가 너무 넓어서 unsigned long long을 사용해야 저장할 수 있습니다. 그리고 처음에 두 번 구할 때 직접log로 구했는데 결과적으로 n은 매우 큰 오차가 있기 때문입니다.인터넷에서 다른 사람의 코드를 보니 1ULL이라는 것이 있다는 것을 알았고, 1ULL을 사용하면 왼쪽으로 63자리로 이동할 수 있었다.
코드:

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

unsigned long long n;

unsigned long long solve(unsigned long long n) {
	unsigned long long m;
	while ((1ULL<<m) < n) {m++;}
	if ((1ULL<<m) == n) return m;
	n = (1ULL<<m) - n - 1;
	if (n < m - 1) return 0;
	else n -= m - 1;
	if (n < m - 2) return 1;
	else n -= m - 2;
	for (unsigned long long k = 1; ; k++) {
		unsigned long long len = (1ULL<<k);
		for (unsigned long long i = 0; i < m - k - 2; i++) {
			if (n < len)
				return solve(2 * len - n);
			else n -= len;
		}
	}
}

int main() {
	while (cin >> n && n) {
		cout << solve(n) << endl;
	}
	return 0;
}