Binary Number
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1879 Accepted Submission(s): 1133
Problem Description
For
2 non-negative integers x and y, f(x, y) is defined as the number of
different bits in the binary format of x and y. For example, f(2,
3)=1,f(0, 3)=2, f(5, 10)=4. Now given 2 sets of non-negative integers A
and B, for each integer b in B, you should find an integer a in A such
that f(a, b) is minimized. If there are more than one such integer in
set A, choose the smallest one.
2 non-negative integers x and y, f(x, y) is defined as the number of
different bits in the binary format of x and y. For example, f(2,
3)=1,f(0, 3)=2, f(5, 10)=4. Now given 2 sets of non-negative integers A
and B, for each integer b in B, you should find an integer a in A such
that f(a, b) is minimized. If there are more than one such integer in
set A, choose the smallest one.
Input
The
first line of the input is an integer T (0 < T ≤ 100), indicating
the number of test cases. The first line of each test case contains 2
positive integers m and n (0 < m, n ≤ 100), indicating the numbers of
integers of the 2 sets A and B, respectively. Then follow (m + n)
lines, each of which contains a non-negative integers no larger than
1000000. The first m lines are the integers in set A and the other n
lines are the integers in set B.
first line of the input is an integer T (0 < T ≤ 100), indicating
the number of test cases. The first line of each test case contains 2
positive integers m and n (0 < m, n ≤ 100), indicating the numbers of
integers of the 2 sets A and B, respectively. Then follow (m + n)
lines, each of which contains a non-negative integers no larger than
1000000. The first m lines are the integers in set A and the other n
lines are the integers in set B.
Output
For each test case you should output n lines, each of which contains the result for each query in a single line.
Sample Input
2
2 5
1
2
1
2
3
4
5
5 2
1000000
9999
1423
3421
13245
353
Sample Output
1
2
1
1
1
9999
Author
CAO, Peng
Source
解析：本题考查位运算。关键在于求x和y的二进制不同位的个数，即x^y的二进制中1的个数。可以用如下方法快速求出：
int cal(int x)
{
int cnt = ;
while(x){
++cnt;
x &= (x-);
}
return cnt;
}
这段代码的核心在于每执行一次x &= (x-1)，会将x的二进制中最低位的1变为0。
运用这个原理，我们还可以得到判断一个正整数x是否为2的n(n>=0)次幂的方法：如果(x&(x-1)) == 0，则为true；否则为false。
常用的位运算还有x&1、x&(-x)等。
x&1：x为奇数则结果为1，x为偶数则结果为0。
x&(-x)：取出x的二进制中低位起，第一个1所在位置代表的数(若x的二进制中不存在1，即x为0，结果为0)。
#include <cstdio>
#include <algorithm>
using namespace std; int T;
int m,n;
int A[],b; int cal(int x)
{
int cnt = ;
while(x){
++cnt;
x &= (x-);
}
return cnt;
} int main()
{
scanf("%d",&T);
while(T--){
scanf("%d%d",&m,&n);
for(int i = ; i<m; ++i)
scanf("%d",&A[i]);
sort(A,A+m);
for(int i = ; i<n; ++i){
scanf("%d",&b);
int min_cnt = 0x7fffffff;
int ans;
for(int j = ; j<m; ++j){
int cnt = cal(b^A[j]);
if(cnt<min_cnt){
min_cnt = cnt;
ans = A[j];
}
}
printf("%d\n",ans);
}
}
return ;
}