金色十月线上编程比赛第二题：解密
题目详情 小强是一名学生， 同时他也是一个黑客。 考试结束后不久，他惊讶的发现自己的高等数学科目居然挂了，于是他果断入侵了学校教务部网站。在入侵的过程中，他发现了与成绩相关的内容是一个加密文件，这个文件由 n 个数构成，经过分析，这个加密文件的密钥为这 n 个数中二进制位数 1 最少的数。但由于数比较多，小强 希望你能帮他得到密钥，好在成绩公布之前将成绩改过来。 输入描述： 输入由多组数据构成，每组数据第一行为一个数 n(1<=n<=10^5)，表示数的数量，第二行 n 个整数表示文件中的每个数(1<=每个数<=10^9)。以文件结尾。 输出描述：
对于每组数据输出一行，先输出数据组数，再输出二进制中含 1 最少的数，如果有多个数符合条件，输出最小的那个。
答题说明 输入样例： 5 3 2 4 5 6 输出样例：
Case 1: 2
对于这道题，有一个技巧就是，一个数和它的掩码进行与运算的话，那么就会将这个数最右边的1给抹掉，什么意思呢，我们举个例子：
假设有x=14，对应的二进制为1110，
14 & 13 => 1110 & 1101 => 1100 (十进制12)
12 & 11 => 1100 & 1011 => 1000(十进制8)
8 & 7 => 1000 & 0111 => 0000(十进制0)
这里执行的次数一共是3次，因此原数14中有3个1
因此这里借鉴这个思想我们来完成此题，算法如下所示（c++ accepted）：
#include <iostream>
using namespace std;
int a[100000];
void main()
{
int n,m=1,i;
while(cin>>n) {
for(i=0;i<n;i++)
cin>>a[i];
unsigned int mincount=0xffffffff;
unsigned int min=0xffffffff;
for(i=0;i<n;i++) {
int tmp=a[i];
int count=0;
while(tmp) {//这里训话求解1的个数
tmp=tmp&(tmp-1);
count++;
}
if(count<mincount) {
mincount=count;
min=a[i];
}
else if(count==mincount)//注意这里1个数相等时输出最小值
min=min>a[i]?a[i]:min;
}
cout<<"Case "<<m<<": "<<min<<endl;
m++;
}
} 本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2014年10月24日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读