分享一下今日头条的在线笔试编程题第二题的一些思路

    是不是觉得有点水贴的意思，刚才发了个第一题，现在又第二题。大家是不是会想起和鲁迅先生的两颗枣树的例子一样呢，有点高抬自己
啦，切回正题。（此题，我没时间调试啦，只是分享一些思路)
    第二题的提示点：
   1.题目提示，如果两两异或，会出现n(n-1)/2种情况。是不是很多人采取双层循环啦，然后ac就30%。
    2.注意最大的输入个数n，是小于10^5，换成2进制，也才17位，2^16=65536
    3.异或时其实是2进制下的运算。
    分享自己的思路：
    1.弄清楚怎么样的两个数异或会大于一个数，异或的两个肯定转为2进制，位数是不一样，一个大于等于目标数转为2进制的位数，一个小于，
    或者两个都大于，当然还得满足两个数转为2进制的位数不一样。
    2.设置一个hashtable，记录转为二进制的位数，其实就是一个长度为18的数组，记录相应位数的个数。
    3.找到位数小于目标数的个数，和大于的个数，两个相乘就是一部分结果，再加上位数大于目标数量的两两相乘，就应该是结果，当然也不
    一定对，因为我没验证，哈哈，只是自己的思路啊
    代码如下(我忽略一种情况，可能还有其他问题，欢迎各位发散自己的思路，我只是提供一些自己思路，相互学习而已)：
#include <iostream>
#include <vector>
using namespace std;
/*
获得一个数转为二进制后的位数
*/
int getNum(int num)
{
	int count = 0;
	while (num)
	{
		++count;
		num /= 2;
	}
	return count;
}
/*
主要处理程序
*/
int biggerThanM1(vector<int> v, int n, int m)
{
	int count = 0;
	//获得目标数的二进制位数
	int mWei = getNum(m);
	//记录位数的数量的数组
	/*
	如6 5 10
	相对应的二进制位数就是3 3 4
	d的下标为3就有两个
	*/
	vector<int> d;
	//初始化
	for (int i = 0; i < 18; i++)
	{
		d.push_back(0);
	}
	//统计输入的数的二进制位数
	for (int i = 0; i < n; i++)
	{
		int tmp = getNum(v[i]);
		++d[tmp];
	}
	//记录大于等于目标数的二进制位数
	int bigM = 0;
	//记录小于等于目标数的二进制位数
	int smallM = 0;
	//获得小于等于目标数的二进制位数
	for (int i = 0; i < mWei; i++)
	{
		smallM += d[i];
	}
	//获得大于等于目标数的二进制位数
	for (int j = mWei; j < 18; j++)
	{
		bigM += d[j];
	}
	/*
	小于位数的与大于位数相乘，得到一部分结果
	比如6 二进制是110
	10 二进制是1010
	这里忽略一种情况就是1010与10异或完其实是小于10的
	*/
	count += smallM * bigM;
	//记录大于位数两两异或的情况
	/*
	最高位最少差一，那就肯定比目标数大，比如10是1010,16是10000异或完最高位肯定是1，位数而且大于目标数
	*/
	vector<int> c;
	for (int k = mWei; k < 18; k++)
	{
		if (d[k])
		{
			c.push_back(d[k]);
		}
	}
	int sum = 0;
	for (int i = 0; i < c.size() - 1; i++)
	{
		for (int j = i + 1; j < c.size(); j++)
		{
			sum += c[i] * c[j];
		}
	}
	count += sum;
	return count;
}
int main3()
{
	int n, m;
	vector<int> v;
	while (cin >> n >> m)
	{
		v.clear();
		int num;
		for (int i = 0; i < n; i++)
		{
			cin >> num;
			v.push_back(num);
		}
		int count = biggerThanM1(v, n, m);
		cout << count << endl;
	}
	system("pause");
	return 0;
}