徐州建设局官网_西安推广公司_百度站长_seo外链优化培训

1.基础知识

&：有0是0

|：有1是1

^：相同为0，相异为1

2.题目

1.求一个数1的个数

1的个数，可以利用&有0就是 0的性质，可以让数每次右移一位与1做&运算，如果最后一位为1则是1，否则是0

#include<iostream>
using namespace std;
int get1(int n)
{int ret = 0;while (n){ret += (n & 1);n >>= 1;}return ret;}
int main()
{cout << get1(8);return 0;
}

2.计算从1到n中所有数二进制中1的个数，列成数组

两个性质，第一个是奇数的1的个数是它二分之一的数的1的个数加一，偶数则相同，另一个是一个数1的个数比它&它-1的1的个数多1 

#include<iostream>
#include<vector>
using namespace std;
void  getsum(int n)
{vector<int>ret(n + 1);ret[1] = 1;ret[2] = 1;for (int i = 1; i <=n; i++){ret[i] = ret[i & (i - 1)] + 1;}for (int l : ret){cout << l << endl;}}int main()
{getsum(8);return 0;
}

另一种方法

#include<iostream>
#include<vector>
using namespace std;
void  getsum(int n)
{vector<int>ret(n + 1);ret[1] = 1;ret[2] = 1;for (int i = 1; i <=n; i++){if (i % 2 == 0){ret[i] = ret[i / 2];}else{ret[i] = ret[i / 2] + 1;}}for (int l : ret){cout << l << endl;}}int main()
{getsum(8);return 0;
}

3.只出现一次的数

使用^的性质，一个数^自己为0，一个数^0为该数

#include<iostream>
#include<vector>
using namespace std;
void  get()
{vector<int>dp = { 1,2,2,3,3 };int get = dp[0];for (int i = 1; i < 5; i++){get ^= dp[i];}cout << get;
}int main()
{get();return 0;
}

  位图，统计两个字符串相同英文字母的个数

#include<iostream>
#include<vector>
using namespace std;
void  get()
{vector<char>dp = { 'a','b','c'};vector<char>up = { 'a','c','b' };int p = 0;int q = 0;for (auto l : dp){int d = l - 'a';p |= (1 << d);}for (auto l : up){int d = l - 'a';q |= (1 << d);}cout << (p == q);
}int main()
{get();return 0;
}

异或和的应用，两个消失的数字

#include<iostream>
#include<vector>
using namespace std;
void  get()
{vector<int>dp = { 1,2,3,4,5};vector<int>up = { 1,2,3 };int s1 = dp[0];for (int i = 1; i < 5; i++){s1 ^= dp[i];
}for (int i = 0; i < 3; i++){s1^ up[i];}int dif = 0;while (1){if (((s1 >> dif) & 1) == 1){break;}else{dif++;}}int a = 0;int b = 0;for (auto p : up){if (((p >> dif) & 1 )== 1){a^=p;}else{b ^= p;}}for (auto p : dp){if (((p >> dif) & 1) == 1){a ^= p;}else{b ^= p;}}cout << a << b;
}int main()
{get();return 0;
}