所有数据在内存中都是以二进制形式存放的，其中有一些位是 1，而另一些位是 0。
例如，整数 100 的二进制表示为 1100100，其中 1 的位数是 3；整数 15 的二进制表示为 1111，其中 1 的位数是 4；整数-15 的 64 位二进制表示为 1111111111111111111111111111111111111111111111111111111111110001，其中 1 的位数是 61。
现在有 N 个整数，要求按照 64 位二进制补码表示中 1 的位数从大到小进行排序。若两个数的二进制表示中 1 的位数相同，则按照数本身值由小到大排序。
例如：数 100,15,0,30,7,-15,100,-100 排序后的结果为 :
-15,-100,15,30,7,100,100,0。
Input
第 1 行：整数 T (1≤T≤10) 为问题数
第 2 行：第一个问题中的 N(1≤N≤10000)
第 3 行：N 个待排序的数 (-1018≤数≤1018)，每两个数之间由一个空格分隔。
第 4 ∽T*2+1 行：后面问题的数据，格式与第一个问题相同。
Output
对于每个问题，输出一行问题的编号（0 开始编号，格式：case #0: 等），然后在一行中输出排序后的数。格式为：以一个空格分隔每两个数。最后一个数后面没有空格。
#include
#include
#include
struct data
{
long long int a; //整数
int number; //64位二进制补码中1的位数
};
int cmp (const void *a, const void *b)
{
struct data d1, d2;
d1 = *((struct data *)a);
d2 = *((struct data *)b);
if (d2.number != d1.number)
return d2.number - d1.number; //降序排列
else{
if (d1.a < d2.a) // 因为cmp返回值为int 而 a为long long 所以不能直接相减
return -1;
else
return 1;
}
}
int main (void)
{
int n;
struct data p[1000];
scanf("%d", &n);
for (int i = 0; i < n; i++){
scanf("%I64d", &p[i].a);
int d=1;
p[i].number = 0;
for (int t=0; t<64;t++){
if(p[i].a & d)
p[i].number++;
d = d << 1;
}
}
int i;
qsort(p,n, sizeof(p[0]), cmp);
for (i = 0; i < n - 1; i++)
printf("%I64d ",p[i].a);
printf("%l64d\n",p[i].a);
}