[UVA][排列組合] 10232 - Bit-wise Sequence
| 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
Input consists of several lines specifying one non-negative integer value for n.
Output
Output should follow the same format as the input except that n is replaced by Bn.
Sample Input
0 1 2 31 32
Sample Output
0 1 2 1073741824 3
題目描述：
將 31 bits 的所有數字，按照 bits 個數大小再按照數字大小排序，得到它們的大小關係。
現在逆向反求，給定第幾個，輸出該數字為何。
#include <stdio.h>
long long C[50][50] = {};
void init() {
C[0][0] = 1;
int i, j, k;
for(i = 1; i < 50; i++) {
C[i][0] = 1;
for(j = 1; j <= i; j++)
C[i][j] = C[i-1][j] + C[i-1][j-1];
}
}
int main() {
init();
long long n;
while(scanf("%lld", &n) == 1) {
long long ret = 0;
int i, j, k;
int ones;
for(i = 0; i <= 31; i++) {
if(n < C[31][i]) {
ones = i;
break;
}
n -= C[31][i];
}
for(i = 31; i >= 0; i--) {
if(C[i][ones] > n)
ret = ret << 1;
else
ret = ret << 1 | 1, n -= C[i][ones], ones--;
}
printf("%lld\n", ret);
}
return 0;
}