详见国家集训队2009论文集 14.刘聪 <<浅谈数位类统计问题>>
这到题需要非常注意复数的操作，其实完全可以讲负数转化为整数操作
也就是int转换成unsigned int
还有就是要注意，int型正数，右移补0，负数右移是补1的，
1
2 /*
3 * SOUR:spoj1182
4 * ALGO:dp, number theory, binary search
5 * DATE: 2010年 06月 08日 星期二 19:47:51 CST
6 * COMM:5
7 * */
8 #include<iostream>
9 #include<cstdio>
10 #include<cstdlib>
11 #include<cstring>
12 #include<algorithm>
13 #include<queue>
14 #include<vector>
15 #include<map>
16 using namespace std;
17 #define pb(x) push_back(x)
18 //#define X first
19 //#define Y second
20 typedef vector < int >vi;
21 typedef pair < int, int >pii;
22 typedef long long LL;
23 typedef unsigned long long ULL;
24 typedef unsigned int uint;
25
26 template <class T> void ckmin(T &a,T b) { if (a > b) { a = b; } }
27 template <class T> void ckmax(T &a,T b) { if (a < b) { a = b; } }
28 int countbit(int n) { return n == 0 ? 0 : 1 + countbit(n & (n - 1)); }
29
30 const int maxint = 0x7fffffff;
31 const long long max64 = 0x7fffffffffffffffll;
32 int cnt[40][40], sum[40];
33 int X, Y, K;
34
35 void pre()
36 //算出cnt[长度][含多少个1]的方案数
37 {
38 int i,j;
39 cnt[0][0] = 1;
40 for (i = 1;i <= 32;i++) {
41 cnt[i][0] = cnt[i-1][0];
42 for (j = 1;j <= 32;j++) {
43 cnt[i][j] = cnt[i-1][j] + cnt[i-1][j-1];
44 }
45 }
46 }
47
48 int num[40], top;
49 int summ(uint X, int R, bool flag = false)
50 {
51 memset(num, 0, sizeof(num));
52 top = 1;
53 while (X) {
54 num[top++] = X & 1;
55 X >>= 1;
56 }
57 if (flag) {
58 for (int i = 1;i <= top;i++) {
59 if (num[i] == 0) {
60 num[i] = 1;
61 for (int j = i - 1;j >= 1;j--) {
62 num[j] = 0;
63 }
64 if (i == top) { top++; }
65 break;
66 }
67 }
68 }
69 int ans = 0, one = 0, i;
70 for (i = top - 1;i >= 1;i--) {
71 if (R >= one && num[i] == 1) {
72 ans += cnt[i - 1][R - one];
73 one++;
74 }
75 }
76 return ans;
77 }
78
79 int summarize(uint X, uint Y, int digit)
80 //[X, Y] 中1的个数为digit的 数字个数
81 { return summ(Y, digit, 1) - summ(X, digit, 0); }
82
83 void proc()
84 {
85 int i, j, one = -1;
86 memset(sum, 0, sizeof(sum));
87 for (i = 0;i < 32;i++) {
88 sum[i] = summarize(X, Y, i) ;
89 if (K > sum[i]) {
90 K -= sum[i];
91 }else {
92 one = i;
93 break;
94 }
95 }
96 if (Y < X) { swap(X, Y); }
97 int left = X, right = Y;
98 while (left < right) { //binary search the value expected
99 int mid = (left + right + 1) / 2;
100 if (summarize(X, mid, one) <= K) {
101 left = mid;
102 }else {
103 right = mid - 1;
104 }
105 }
106 while (countbit(left) != one) { left --; } // attention
107
108 int ans = 0;
109 for (i = 0;i < 32;i++) {
110 if (left & (1 << i)) {
111 ans |= 1 << i;
112 }
113 }
114 printf("%d\n", ans);
115 }
116
117 int main()
118 {
119 int i, j, testcase;
120 pre();
121 scanf("%d", &testcase);
122 while (testcase-- ) {
123 scanf("%d %d %d", &X, &Y, &K);
124 proc();
125 }
126 return 0;
127 }
128