位运算（算法5）

常见位运算总结

五道位运算入门规律题 

1.位1的个数

link：191. 位1的个数 - 力扣（LeetCode）
key：n &= (n-1))可以消去右1； 
code

1. class Solution {
2. public:
3.     int hammingWeight(int n) {
4.         int ans = 0;
5.         while(n)
6.         {
7.             ++ans;
8.             n &= (n-1);
9.         }
10.         return ans;
11.     }
12. };

复制代码

2.比特位计数

link：338. 比特位计数 - 力扣（LeetCode）
分奇偶后动态规划
code：

1. class Solution {
2. public:
3.     vector<int> countBits(int n) {
4.         //分奇偶即可
5.         vector<int> ans(n+1);
6.         ans[0] = 0;
7.         for(int i = 1; i <= n; i++)
8.         {
9.             if(i%2==1) ans[i] = ans[i-1] + 1;
10.             else ans[i] = ans[i>>1];
11.         }
12.         return ans;
13.     }
14. };

复制代码

3.汉明间隔

link:461. 汉明间隔 - 力扣（LeetCode）
code

1. class Solution {
2. public:
3.     int hammingDistance(int x, int y) {
4.         int ret = x ^ y;
5.         int ans = 0;
6.         while(ret)
7.         {
8.             ++ans;
9.             ret &= (ret-1);
10.         }
11.         return ans;
12.     }
13. };

复制代码

4.只出现一次的数字I

link:136. 只出现一次的数字 - 力扣（LeetCode）
code

1. class Solution {
2. public:
3.     int singleNumber(vector<int>& nums) {
4.         int ans = 0;
5.         for(const auto& e:nums)
6.         {
7.             ans ^= e;
8.         }
9.         return ans;
10.     }
11. };

复制代码

5.只出现一次的数字III

link:260. 只出现一次的数字 III - 力扣（LeetCode）
code

1. class Solution {
2. public:
3.     vector<int> singleNumber(vector<int>& nums) {
4.         //只要可以把nums分成两批, 每批只有一个所求答案，就可以转化为《只出现一次的数字》
5.         //通过ans[x >> ctz & 1] ^= x实现
6.         int ret = 0;
7.         for(const auto&e:nums)
8.         {
9.             ret^=e;
10.         }
11.         vector<int> ans = {0, 0};//={ret, ret};
12.         int ctz = __builtin_ctz(ret);//对于ret>>ctz&1， ans中两元素肯定不一样
13.         for(const auto&e:nums)
14.         {
15.             ans[(e>>ctz)&1]^=e;
16.         }
17.         return ans;
18.     }
19. };

复制代码

1.判定字符是否唯一

link:面试题 01.01. 判定字符是否唯一 - 力扣（LeetCode）
key:
        位图取代哈希表
code

1. class Solution {
2. public:
3.     int bit = 0;//位图代替hash数组
4.     bool find(int num)
5.     {
6.         return (bit>>num) & 1;
7.     }
8.     void bset(int num)
9.     {
10.         bit |= (1<<num);
11.     }
12.     bool isUnique(string astr) {
13.         int len = astr.size();
14.         if(len > 26) return false;
15.         for(auto &e:astr)
16.         {
17.             if(find(e-'a')) return false;
18.             bset(e-'a');
19.         }
20.         return true;
21.     }
22. };

复制代码

2.丢失的数字

link:268. 丢失的数字 - 力扣（LeetCode）
key:
        制造条件，运用异或性质找到单身汉
code

1. class Solution {
2. public:
3.     int missingNumber(vector<int>& nums) {
4.         int ans = 0;
5.         for(int i = 0; i <= nums.size(); i++)
6.         {
7.             ans ^= i;
8.         }
9.         for(const auto& e: nums)
10.         {
11.             ans ^= e;
12.         }
13.         return ans;
14.     }
15. };

复制代码

3.两整数之和

link:371. 两整数之和 - 力扣（LeetCode）
key:
        利用^计算不进位相加
        利用&计算进位
code

1. class Solution {
2. public:
3.     int getSum(int a, int b) {
4.         //利用异或运算性质：不进位相加
5.         //  按位与性质可用来寻找进位
6.         int x = (a^b);
7.         int y = (a&b)<<1;
8.         while(y)
9.         {
10.             a = x;
11.             b = y;
12.             x = (a^b);
13.             y = (a&b)<<1;
14.         }
15.         return x;
16.     }
17. };

复制代码

4.只出现一次的数字II

link:137. 只出现一次的数字 II - 力扣（LeetCode）
key:
        以bite位为单位看待数字
        以bite位为单位做计算（+/-）操纵
code

1. class Solution {
2. public:
3.     int singleNumber(vector<int>& nums) {
4.         // 以比特位为单位看待数字
5.         int ans = 0;
6.         for(int i = 0; i < 32; i++)
7.         {
8.             int sum = 0;
9.             for(const auto& e:nums)//求nums第i的bite位和
10.             {
11.                 sum+=((e>>i)&1);
12.             }
13.             sum %= 3;
14.             if(sum==1) ans |= (1<<i);
15.         }
16.         return ans;
17.     }
18. };

复制代码

5.消散的两个数字

link:面试题 17.19. 消散的两个数字 - 力扣（LeetCode）
key:
        同《只出现一次的数字III》
        __builtin_ctz 加 ans[x >> ctz & 1] ^= x
code

1. class Solution {
2. public:
3.     vector<int> missingTwo(vector<int>& nums) {
4.         vector<int> ans={0, 0};
5.         int ret = 0;
6.         
7.         for(const auto& e:nums)
8.         {
9.             ret ^= e;
10.         }
11.         for(int i = 1; i <= nums.size()+2; i++)
12.         {
13.             ret ^= i;
14.         }
15.         int ctz = __builtin_ctz(ret);
16.         for(int i = 1; i <= nums.size() + 2; i++)
17.         {
18.             ans[(i>>ctz)&1] ^= i;
19.         }
20.         for(const auto& e:nums)
21.         {
22.             ans[e>>ctz&1] ^= e;
23.         }
24.         return ans;
25.     }
26. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。