1622. [SPOJ 1182] 二进制列排序

【题目描述】

让我们考虑m到n（含m,n）的所有整数i的32位二进制表示（m<=i<=n,m*n>=0,-2^31<=m<=n<=2^31-1）。注意，负数由32位补码表示。也就是说，一个负数的二进制表示与其相反数的二进制表示之和恰好等于2^32（二进制的1 0000 0000 0000 0000 0000 0000 0000 0000）

例如，6的32位二进制表示是0000 0000 0000 0000 0000 0000 0000 0110

-6的32位二进制表示是1111 1111 1111 1111 1111 1111 1111 1010

因为

0000 0000 0000 0000 0000 0000 0000 0110 (6)

+

1111 1111 1111 1111 1111 1111 1111 1010 (-6)

-------------------------------------------------

= 1 0000 0000 0000 0000 0000 0000 0000 0000 (2^32)

让我们将这些整数的32位二进制表示排序。排序方法是：先按照二进制表示中1的个数从小到大排，1的个数相同的32位二进制数按字典序排。注意，它们的长度都是32位。

例如，当m=0,n=5时，排序的结果如下：

当m=-5,n=-2时，排序的结果如下：

给出m，n，k（1<=k<=n-m+1），你的任务是写一个程序找到排序后m~n的整数中第k小的数。

【输入格式】

输入包含多组数据。

输入文件的第一行是一个不超过1000的正整数，代表数据组数。

接下来是若干组数据。

每组数据有一行3个空格隔开的整数m,n,k。数据范围见题目描述。

【输出格式】

对每组数据，输出排序后第k小的数。

【样例输入】

2
0 5 3
-5 -2 2

【样例输出】

2
-5

【提示】

原题中k<=2147473547，但这里的k值有可能大于这个数。

【来源】

SPOJ 1128 Sorted bit squence

ACM ICPC 2006, Asia Regional Contest, site Hanoi