算法思考：位运算

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; }