位运算---总结

位运算
基础

1. 1. & 运算符 : 有 0 就是 0
2. 2. | 运算符 : 有 1 就是 1
3. 3. ^ 运算符 : 相同为0 相异为1 and 无进位相加

复制代码

• 位运算的优选级
  
  1. 不用在意优先级,能加括号就加括号

  复制代码
• 给一个数 n ,确定它的二进制位中第 x 位是 0 照旧 1?
  

1. 规定: 题中所说的第x位指:int 在32位机器下4个字节32位,从右向左依次增加,从0位开始,即 第 0 位 到第 31 位.
2. (n >> x) & 1

复制代码

• 将一个数 n 的二进制位表现的第 x 位修改为 1
  

1. n |= (1 << x)

复制代码

• 将一个数 n 的二进制表现的 第 x 位修改为 0
  

1. n &= ~(1 << x)

复制代码

• 提取一个数 n 二进制表现中最右侧的1
  

1. n & -n;
2. -n : 将最右侧的1左边的区域全部变为相反数，右边的1的数不变（本来就是0）
3.     0 1 1 0 1 0 1 0 0 0
4. ~   1 0 0 1 0 1 0 1 1 1
5. +1  1 0 0 1 0 1 1 0 0 0
6. n:  0 1 1 0 1 0 1 0 0 0
7. ------------------------
8.         0 0 0 0 0 0 1 0 0 0

复制代码

• 干掉一个数( n )二进制表现中最右侧的1
  

1. n &= (n -1)

复制代码

• 异或(^)运算的运算律
  

1. 1. a ^ 0 = a;
2. 2. a ^ a = 0; 消消乐
3. 3. a ^ b ^ c = a ^ (b ^ c) 符合交换律和结合律
5. 异或
6. 无进位相加解释:
7. 1 0 1 1 0 1 0
8. 0 0 1 0 1 0 1
9. 1 0 1 0 0 0 0
10. -------------
11. 0 0 1 1 1 1 1   --> 两个 1 会消消乐(本质就是1的抵消), 即无进位相加

复制代码

标题训练
191.位1的个数

1. 思绪一:依次判断每个位是否为1,为 1 ans++;class Solution {public:    int hammingWeight(int n) {        int ans = 0;        int sum = 32;        for(int i = 0; i < 32; i++)        {            if((n >> i) & 1)            {                ans++;            }        }        return ans;    }};思绪二:依次消除最低位的 1, 消除一次 ans++;class Solution {public:    int hammingWeight(int n) {        int ans = 0;        while(n)        {            n &= (n -1)
2. ;            ans++;        }        return ans;    }};

复制代码

338. 比特位计数

1. 思路:依次消除最低位的 1, 消除一次 count++; 对每个数字统计一次即可
2. class Solution {
3. public:
4.     vector<int> countBits(int n) {
5.         vector<int> ans;
6.         for(int i = 0; i <= n; i++)
7.         {
8.             int count = 0;
9.             int temp = i;
10.             while(temp)
11.             {
12.                 temp &= (temp - 1);
13.                 count++;
14.             }
15.             ans.push_back(count);
16.         }
17.         return ans;
18.     }
19. };

复制代码

461. 汉明隔断

1. //思路:先异或(相同为0相异为1)后统计1的个数
2. class Solution {
3. public:
4.     int hammingDistance(int x, int y) {
5.         x ^= y;
6.         int ans = 0;
7.         while(x)
8.         {
9.             x &= (x -1);
10.             ++ans;
11.         }
12.         return ans;
13.     }
14. };

复制代码

136. 只出现一次的数字

1. //思路:利用异或运算规律:
2. // 1. a ^ a = 0;
3. // 2. a ^ 0 = a
4. // 3. 交换律和结合律
5. class Solution {
6. public:
7.     int singleNumber(vector<int>& nums) {     
8.         int ans = 0;
9.         for(int iter : nums)
10.         {
11.             ans ^= iter;
12.         }
13.         return ans;
14.     }
15. };

复制代码

260. 只出现一次的数字 III

1. //思路:利用异或的规律,将所有数据异或一次,结果一定是只出现一次的两个元素异或后的结果,然后利用异或的相同为 0 相异为 1,并用最低位 1 来区分两个只出现一次的元素,划分为两个集合(此时每个集合中只有一个数出现一次,其他数都出现了两次),分别异或即可得到结果
2. class Solution {
3. public:
4.     vector<int> singleNumber(vector<int>& nums) {
5.         unsigned int xor_all = 0;
6.         //为什么使用unsigned int ？
7.         //使用int可能会导致溢出
8.         //unsigned int 自动会进行模运算,保证结果始终在unsigned int 表示范围内
9.         //int: (-2^31 到 2^31 - 1)
10.         //unsigned int: (0 ~ 2^32 -1)
11.         for(int iter : nums)
12.         {
13.             xor_all ^= iter;
14.         }
15.         //获取异或结果的最低位为 1 的位
16.         int lowbit = xor_all & (-xor_all);
17.         vector<int> ans(2);
18.         for(int x : nums)
19.         {
20.             if((x & lowbit) == 0)
21.             {
22.                 ans[1] ^= x;
23.             }
24.             else
25.             {
26.                 ans[0] ^= x;
27.             }
28.         }
29.         return ans;
30.     }
31. };

复制代码

口试题 01.01. 判定字符是否唯一

1. 思路:使用hash表统计每个字符出现的次数,然后遍历hash表即可
2. class Solution {
3. public:
4.     bool isUnique(string astr) {
5.         unordered_map<char,int> hash;
6.         for(int i = 0; i < astr.size(); i++)
7.         {
8.             hash[astr[i]]++;
9.         }
10.         for(auto iter : hash)
11.         {
12.             if(iter.second > 1)
13.             {
14.                 return false;
15.             }
16.         }
17.         return true;
18.     }
19. };
21. class Solution {
22. public:
23.     bool isUnique(string astr) {
24.         //利用位图思想来解决问题
25.         if(astr.size() > 26)
26.         {
27.             return false;
28.         }
29.         int bitmap = 0;
30.         for(char c : astr)
31.         {
32.             int n = c - 'a';
33.             //判断字符是否已经出现过
34.             if(bitmap & (1 << n))
35.             {
36.                 return false;
37.             }
38.             else
39.             {
40.                 bitmap |= (1 << n);
41.             }
42.         }
43.         return true;
44.     }
45. };

复制代码

268. 丢失的数字

1. //利用异或的规则:将0~n的数字和 nums中的数字都异或一次结果即为没有出现的那个数,其他数都出现了两次
2. class Solution {
3. public:
4.     int missingNumber(vector<int>& nums) {
5.         unsigned int xor_all = 0;
6.         int n = nums.size();
7.         for(int i = 0; i <= n; i++)
8.         {
9.             xor_all ^= i;
10.         }
11.         for(int x : nums)
12.         {
13.             xor_all ^= x;
14.         }
15.         return xor_all;
16.     }
17. };

复制代码

371. 两整数之和

1. //思路:先使用无进位相加,计算进位,无进位相加直到进位为0
2. class Solution {
3. public:
4.     int getSum(int a, int b) {
5.         while(b != 0)
6.         {
7.             int x = a ^ b;//计算无进位相加
8.             int carry = ( a & b) << 1; ;//计算进位
9.             a = x;
10.             b = carry;
11.         }
12.         return a;
13.         
14.     }
15. };

复制代码

137. 只出现一次的数字 II

1. //思路:统计每个数字第i位的和sum, sum %= 3 即可判断只出现一次的数字第i位
2. //3n 0 + 0 = 0  %=3 == 0
3. //3n 0 + 1 = 1  %=3 == 1
4. //3n 1 + 1 = 3n + 1 %3 == 1
5. //3n 1 + 0 = 3n  %=3 == 1  -->此方法可推广到n,即除某个元素只出现一次外,其他元素都出现了n次,%=n 即可判断只出现一次的数字的第i位
6. class Solution {
7. public:
8.     int singleNumber(vector<int>& nums) {
9.         int ans = 0;
10.         for(int i = 0; i < 32; i++)
11.         {
12.             int sum = 0;
13.             for(int x : nums)
14.             {
15.                 if(x & (1 << i))
16.                 {
17.                     ++sum;
18.                 }
19.             }
20.             sum %= 3;
21.             if(sum == 1)
22.             {
23.                 ans |= (1 << i);
24.             }
25.         }
26.         return ans;
27.     }
28. };

复制代码

口试题 17.19. 消散的两个数字

1. //思路:将所有数字全部异或,转换为题目只出现了一次的数字3
2. class Solution {
3. public:
4.     vector<int> missingTwo(vector<int>& nums) {
5.         unsigned int xor_all = 0;
6.         int n = nums.size();
7.         for(int x : nums)
8.         {
9.             xor_all ^= x;
10.         }
11.         for(int i = 1; i <= n+2; i++)
12.         {
13.             xor_all ^= i;
14.         }
15.         //计算最低位为1的位
16.         int lowbit = xor_all & (-xor_all);
17.         vector<int> ans(2);
18.         for(int x : nums)
19.         {
20.             if((lowbit & x) == 0)
21.             {
22.                 ans[0] ^= x;
23.             }
24.             else
25.             {
26.                 ans[1] ^= x;
27.             }
28.         }
29.         for(int i = 1; i <= n+2; i++)
30.         {
31.             if((lowbit & i) == 0)
32.             {
33.                 ans[0] ^= i;
34.             }
35.             else
36.             {
37.                 ans[1] ^= i;
38.             }
39.         }
40.         return ans;
41.     }
42. };

复制代码

结束!

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