zoj-3870 (二进制)

For an upcoming programming contest, Edward, the headmaster of Marjar University, is forming a two-man team from N students of his university.

Edward knows the skill level of each student. He has found that if two students with skill level A and B form a team, the skill level of the team will be A ⊕ B, where ⊕ means bitwise exclusive or. A team will play well if and only if the skill level of the team is greater than the skill level of each team member (i.e. A ⊕ B > max{A, B}).

Edward wants to form a team that will play well in the contest. Please tell him the possible number of such teams. Two teams are considered different if there is at least one different team member.

Input

There are multiple test cases. The first line of input contains an integer Tindicating the number of test cases. For each test case:

The first line contains an integer N (2 <= N <= 100000), which indicates the number of student. The next line contains N positive integers separated by spaces. The i^thinteger denotes the skill level of i^th student. Every integer will not exceed 10⁹.

<h4< dd="">Output

For each case, print the answer in one line.

<h4< dd="">Sample Input

<h4< dd="">Sample Output

1
6
这题真的做的我失去梦想，成为了一条咸鱼- -；
题目很好理解，就是求有多少种 两个数的异或值大于这两个数 的情况。
赤裸裸的二进制，然鹅，我和我队友都不知道咋处理。
突然我灵光一闪，对他说，我们打表找规律吧！
结果我还真找到了规律，写了一大圈子，想了几个样例还全过了，信誓旦旦交上去 --WA。
（哇的一声哭出来）
然后一脸懵逼对着打的表想样例，咋输，咋对。
又进行 一系列 真·玄学debug 法 果不其然全部 -- WA。
（尴尬又不失礼貌的微笑）

...

好了，回归正题。
这题的正解自然是用二进制思想,思路是判断什么情况下，两个数的异或值会大于这两个数。
显然 1^1=0 1^0=1 0^0=0 那么设需要判断的两个数为a, b且 a<b(如果a=b，则a^b=0)
因为1^0=1，那么只要a的最高位对应在b中的值为0，则满足条件。这样讲比较抽象，举个例子：
b=10110,那么什么情况下 a^b>b 呢？肯定是当a的最高位在b的从左到右第2位，第5位时才会a^b>b，即：
b: 　　10110   10110
a:  　　1xxx       1
异或值：11xxx　 10111 

是吧，这样情况下的异或值都要大于a和b，也就是说只需要设一个book[Max]，把每个数的首位位置记下来，再根据这个记录，判断是否满足情况。
具体看代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int M = 111111;
const int Mx=33;
int nu[M];
int book[Mx];  //记录最高位的位置 
int main(){
	ios::sync_with_stdio(false);
	int t;
	cin>>t;
	while(t--){
		memset(book,0,sizeof(book));
		int n,ans=0;
		cin>>n;
		for(int i=0;i<n;i++){
			cin>>nu[i];
			int l=31; //题目中说数据不超过1e9 
			while(!(nu[i]&(1<<l))) l--;  //从第31位进行进行与运算， 
			book[l]++;  //找到该数二进制首位后，记录 
		}
		for(int i=0;i<n;i++){
			int l=31;
			while(!(nu[i]&(1<<l))) l--;//找nu[i]的二进制首位 
			while(l--){				   //找到二进制首位后，继续遍历 
				if(!(nu[i]&(1<<l)))  //找到该数二进制中的所有0 
				 ans+=book[l];		//把该位是0的book[l]的所有记录相加，便是答案 
			}
	
		}
		cout<<ans<<endl;
	}
	return 0;
}

这题的题解我看的是这个：http://blog.csdn.net/ZzebraA/article/details/51272652