| Problem D: Bit-wise Sequence |
Dr. DoLots is an expert in number theory and he is currently studying prime numbers. In fact, some people say that he has some formula which can generate the prime numbers in increasing order. But, his formula needs to order the non-negative integers according to the increasing number of ones in their binary representation. That is, all non-negative integers with m ones in their binary representation should be ordered before all the non-negative integers with m+1 ones.
More formally, lets define the non-negative integer sequence Bn such that for every
non-negative integers m and n where n<m,
1. either O(Bn)< O(Bm)
2. or O(Bn) = O(Bm)
and Bn<
Bm.
where O(n) is the number of ones in the binary representation of n.
Dr. DoLots wants you to write a program which computes the value of Bn for arbitrary values of n, 0£ n£ 2147483647. For simplicity, we consider only non-negative integers less than 2147483648 to appear in the sequence. You might be wondering why the doctor cannot do it himself. He is very busy and he wants to spent his time on more important things (That is what he says, actually, he is a bit lazy, but you can help him, can't you ?).
Input consists of several lines specifying one non-negative integer value for n.
Output should follow the same format as the input except that n is replaced by Bn.
0 1 2 31 32
0 1 2 1073741824 3