ui软件哪个最好用_网站页面制作公司_做网站比较好的公司有哪些_网站优化排名金苹果系统

前言：

这次的算法分享，我想给大家带来位运算的专题练习，相信大家在学习C语言的时候一定有接触到位运算的操作，包括按位与(&)，按位或(|)，按位异或(^)。
本章是作为开启真正的算法分享之前的补充文章，先铺垫好基础知识，这样在后面分享讲解的时候也能很快就反应过来是怎么一回事。下面就先来介绍8个基础知识，然后会有5道经典的OJ题目让我们来解决。

常见位运算总结：

• 基础位运算：

  1. 左移操作符：<<
  2. 右移操作符：>>
  3. 取反：~
  4. 按位与：& 有0则0
  5. 按位或：| 有1则1
  6. 按位异或：^ 相同为0，相异为1（无进位相加

• 给一个数n，确定它的二进制表示中的第×位是0还是1： (n >> x) & 1

• 将一个数n的二进制表示的第x位修改成1：n &= (1 << x)

• 将一个数n的二进制表示的第x位修改成0：n &= (~(1 << x))

• ==提取==一个数（n）二进制表示中最右侧的1（lowbit）：n & -n

• ==干掉==一个数（n）二进制表示中最右侧的1：n & (n - 1)

• 位运算的优先级：多加括号

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

  1. a ^ 0 == a
  2. a ^ a == 0
  3. (a ^ b) ^ c == (a ^ c) ^ b 异或的交换律
  4. a ^ b == c <==> a ^ c == b

经典OJ：

《位1的个数》

解法思路：

class Solution 
{
public:int hammingWeight(int n) {int count = 0;while(n){if(n & 1 == 1) count++;n >>= 1;}return count;}
};

因为这些题目都比较基础，所以在这里我就简单介绍了。

对于这道题来说，要想统计当前数的二进制位有多少个1，我们只需要不断将二进制位右移一位，再按位与(&)上1，其实右移一位其实就是除以2，按位与(&)上1后判断是否为1就可以判断是否为1.

《比特位计数》

解法思路：

class Solution 
{
public:             vector<int> countBits(int n) {vector<int> ans;for(int i = 0; i <= n; ++i){int tmp = i; // 一定要用临时变量进行保存int count = 0;while(tmp){if(tmp & 1 == 1) count++;tmp >>= 1;}ans.push_back(count);}return ans;}
};

本道题和上一道的逻辑解法是一致的，这里要注意的就是在while循环中，一定要用临时变量tmp来保存i，并且对tmp进行操作，这里一定是要注意的。剩下的功能都是类似的，在这里我就不过多赘述了。

《汉明距离》

解法思路：

class Solution 
{
public:int hammingDistance(int x, int y) {int XOR = x ^ y;int count = 0;while(XOR){if(XOR & 1 == 1) count++;XOR >>= 1;}return count;}
};

这道题的逻辑和前面也是一致的，因为要计算不同二进制比特位的数目，因此我们直接将这两个数进行异或操作，因为异或遵循相异为1，相同为0，所以符合题意。剩下的

《只出现一次的数字》

解法思路：

class Solution 
{
public:int singleNumber(vector<int>& nums){int single = 0;for(const auto& x : nums) single ^= x;return single;}
};

根据异或的性质a ^ a == 0，而且依据异或具有交换性，所以我们很快就能找出只出现一次的数字。

《只出现一次的数字 III》

解法思路：

class Solution
{
public:vector<int> singleNumber(vector<int>& nums) {int XOR = 0;for(const auto& x : nums) XOR ^= x;// 提取最右侧的为1的比特位int lowbit = XOR == INT_MIN ? INT_MIN : (XOR & -XOR);vector<int> n1, n2;for(const auto& x : nums){if((lowbit & x) == 0) n1.push_back(x);else n2.push_back(x);}int q = 0, w = 0;for(const auto& x : n1) q ^= x;for(const auto& y : n2) w ^= y;return {q, w};}
};

针对这道题来说，题目上和上道题目差不多，只是这次我们要查找的是两个只出现一次的数字。

我们先将他们都异或起来，得到的结果XOR就是那两个目标值异或的结果。

XOR的二进制位中如果存在1，那就代表那两个数的同一个二进制位的值是不一样的！！！

所以针对这一点，我们可以认准XOR最右边的1，因此我们使用XOR & -XOR取出最右侧的1。

取出来之后再进去原数组中进行遍历，一个一个的按位与(&)，如果按位与(&)的结果为0，就放在一个数组n1中，若为XOR就放在n2中。

这样就可以很好地将两个目标元素分开了，它们都分别存放在了不同的数组中。
这样我们就只需要分别对n1，n2的每个值进行异或(^)操作，就可以取出那两个值了！

这里还有注意的是，最后的测试用例会有[1,1,0,-2147483648]这么一个测试用例，因为存在一个INT_MIN，这会造成出现溢出

有两种方法：

1. 将XOR的类型设置成unsigned
2. 对XOR进行判断处理 int lowbit = XOR == INT_MIN ? INT_MIN : (XOR & -XOR);