《编程思维与实践》1003.按数据中1的位数排序-爱代码爱编程
《编程思维与实践》1003.按数据中1的位数排序
题目
思路
分两个步骤解决:
1.求出一个数二进制中1的个数——可以通过与1<<j 进行&(按位与)运算累加求得;
2.排序——qsort快排,将1的个数和本身值捆绑起来(运用结构体)。
需要注意的点:
1.一行数据带空格输入时,可以通过多次scanf来进行读取;
2.排序的数可能很大,应该用long long(8个字节,64bit)类型存储,
所以1<<j过程中的1也应为64bit,也是long long类型;
3.在编写cmp时由于返回值是int,所以在比较long long数据时不能简单做差返回。
代码
#include<stdio.h>
typedef struct { long long data; int count;}Number; //data为原数据 count为1的个数
int cmp(const void*a,const void*b)
{
Number *m =(Number*)a;
Number *n =(Number*)b;
if(m->count!=n->count)
{
return (n->count)-(m->count);
}
else{
if(m->data>n->data) //long long 类型
{
return 1;
}
if(m->data<n->data)
{
return -1;
}
}
}
int main()
{
int T;
scanf("%d",&T);
for(int i=0;i<T;i++)
{
int N;
scanf("%d",&N);
Number s[N];
for(int j=0;j<N;j++) //读入数据并初始化
{
scanf("%lld",&s[j].data);
s[j].count=0;
}
for(int j=0;j<N;j++)
{
for(int k=0;k<64;k++)
{
if((s[j].data)&((long long)(1)<<k)) //统计1的个数
{
s[j].count++;
}
}
}
qsort(s,N,sizeof(Number),cmp);
printf("case #%d:\n",i);
for(int j=0;j<N;j++)
{
printf("%lld ",s[j].data);
}
printf("\n");
}
return 0;
}