算法：位运算
- 常见位运算操作
- 基本题型
- 模拟加法
- 数字查找
- 总结
常见位运算操作
在C/C++中，有比较丰富的位运算操作符，常见的有：
&：按位与
|：按位或
~：按位取反
^：按位异或
<<：左移操作符
>>：右移操作符
这些操作符的用法就不详细讲解了，本博客主要围绕算法来讲解。
先概述一下位运算中常会用到的操作与算法。
给一个数
n，求它二进制的第x位是0还是1
只需要将n右移x位，然后与1按位与即可，也就是：
(n >> x) & 1
如果结果是1，那么第x位就是1，反之为0。
给一个数
n，将它二进制的第x位修改为1
如果要把第x位修改为1
-
对于
x以外的位，不能被影响，它们要与0进行按位或。 -
而对于第
x位，想要变成1，就与1按位或
也就是说我们现在要得到x位为1，其他位为0的数据，也就是1 << x。
公式如下：
n |= 1 << x;
给一个数
n，将它二进制的第x位修改为0
如果要把第x位修改为1
-
对于
x以外的位，不能被影响，它们要与1进行按位与。 -
而对于第
x位，想要变成0，就与0按位与
也就是说我们现在要得到x位为0，其他位为1的数据，我们可以对1 << x这个整体进行取反，得到想要的值，也就是~(1 << x)。
公式如下：
n &= ~(1 << x);
给一个数
n，提取它最右侧的1
想得到n最右侧的1，公式为：
n & -n;
此时整个表达式的结果，就只保留了n最右侧的1。
原理如下：
复数在内存的存储机制为：源码取反，然后再+1，如果n的二进制为：00110000那么反码的推演过程为：
00110000
11001111 取反
11010000 +1
取反的时候，所有位变成了相反的位，再进行+1，此时右侧的所有1都变回了0，并且发送进位，此时最右侧的一位1被复原。
最后在和自己进行按位与，最后一位1左侧的所有数都是取反得到的，按位与结果都为0。最后一位1右侧的所有值都是0，按位与结果也为0。这样我们就得到了只保留最右侧的一位1，其余位都变成0的值了。
给一个数
n，把它最右侧的1变为0
想要消除一个数最右侧的一位1，公式为：
n & (n - 1);
在执行n - 1的时候，对于二进制而言，右侧的0就会向高位借位，那么直到借到第一个1为止。最后最右侧的1就会变成0，右侧的所有0都会变成1。
00110000 n
00101111 n - 1
异或运算率
按位异或的常见的运算率如下：
a ^ a = 0;
a ^ 0 = a;
a ^ b ^ c = (a ^ b) ^ c;
也就是自己与自己异或，结果为0；与0异或，值不变；以及异或的交换律。
基本题型
LeetCode 191. 位1的个数
本题要求我们求出一个整型中二进制的1的数目，我们可以直接遍历整数的所有位，然后只要这个位是1就计数一次：
class Solution
{
public:
int hammingWeight(int n)
{
int count = 0;
for (int i = 0; i < 32; i++)
{
if ((n >> i) & 1)
count++;
}
return count;
}
};
该方法通过整型只有32位，来进行每一个位的遍历，但是存在两个缺点：
- 该方法遍历方式过于暴力，把所有的位都检查了一遍
- 该方法只能作用于
int类型数据，不具有普适性
在开头我讲解了如何删除一个整数最右侧的1，那么我们只需要每次都删除一位1，最后n 就会变成0。删除了几次·，那么就有几位1。
代码如下：
class Solution
{
public:
int hammingWeight(int n)
{
int count = 0;
while (n)
{
n &= n - 1;
count++;
}
return count;
}
};
这种写法，每一次都固定消除一位1，提高了效率。另外地，任何长度的整型都可以用这个方法来计算。
LeetCode 338. 比特位计数
本题要求出一个[0, n]所有值的1的个数，并返回一个数组。
对于这道题，可以用暴力的解法，直接遍历数组，每一个数字都单独求一次1的个数。
但是由于数字是连续的，其实我们可以通过前面的值来简化求后面值的操作。
比如说00010010，由于最后一位是0，其+1后，下一位数字00010011刚好比其多一位1。
也就是说：一个奇数的二进制的1的个数，比前面那个数（一定是偶数）的二进制的1的个数多一个。
由于奇数的最后一位一定是1，那么奇数+1一定会发生进位，进位的时候会有1会被消除，而被消除的1的数目是不确定的，因此一个偶数的二进制1的个数，与前面那个数的二进制1的个数，没有必然联系。
但是一个数字×2，其二进制的表现为：所有位整体左移一位。比如00110011乘以二，得到01100110，这个过程只发生移位，1的个数不会改变。而一个偶数一定是2的倍数，所以一个偶数n的二进制的1的个数，等于n/2的二进制的1的个数。
代码逻辑如下：
- 遍历
[0, n]
- 如果当前值
x是偶数，位1的个数等于2/x的位1的个数- 如果当前值
x是奇数，位1的个数比x - 1的位1的个数多一个
代码如下：
class Solution
{
public:
vector<int> countBits(int n)
{
vector<int> ret(n + 1);
ret[0] = 0;
for(int i = 1; i < n + 1; i++)
{
if (i % 2 == 0) // 偶数
ret[i] = ret[i / 2];
else // 奇数
ret[i] = ret[i - 1] + 1;
}
return ret;
}
};
LeetCode 461. 汉明距离
本题要求求出两个整数的不同的位的个数，提到不同的位，这就很明显要使用按位异或了：相同为0，相异为1。
因此我们只需要先让两个数按位异或，然后求结果的1的个数，就是两个数中不同位的个数。
代码如下：
class Solution
{
public:
int hammingDistance(int x, int y)
{
int n = x ^ y;
int ret = 0;
while (n)
{
n &= n - 1;
ret++;
}
return ret;
}
};
模拟加法
LeetCode 371. 两整数之和
本题要求不用+和-完成两数的加法。想要解决这道题，那就要再理解一下按位异或的其他含义了。
按位异或基本规则为：相同为0，相异为1，从数学角度也可以理解为不进位加法。
比如00110011与01010101进行异或：
00110011
01010101
---------
01100110
两个数的最低位都是1，如果执行加法，那么1 + 1 = 2会导致进位，本位余0，向上进1 。但是按位异或 只余0，不进1。
两数的第二位，分别是0和1，如果执行加法，0 + 1 = 1，本位余1，不进位。按位异或也可以理解为只余1，不进位。
因此，按位异或可以理解为一个不进位的加法。
那么现在给我们两个数a和b，我们要用位运算来模拟加法，现在我们可以通过按位异或执行一个不进位的加法。那么进位应该怎么办呢？
如果在二进制计算中发生了进位，那么两个位一定都是1，进位也就是把多出来的1加到高位去。因此我们可以通过按位与a & b，得到两个位都为1的位，也就是需要进位的位。然后将其左移一位(a & b) << 1，来模拟进位。
代码：
class Solution
{
public:
int getSum(int a, int b)
{
while (b)
{
int tmp = a ^ b; // 不进位加法
int carry = (a & b) << 1; // 得到进位
a = tmp;
b = carry;
}
return a;
}
};
我来解析一下以上代码：
在每一轮循环中，先通过a ^ b得到不进位的加法，然后通过(a & b) << 1得到进位。那么现在的任务就是把进位carry加到tmp中，但是我们不能用+，来进行carry + tmp的操作。
这样我们的问题从a + b转化为了carry + tmp。于是把tmp交给a，carry交给b，利用循环继续以上的模拟进位操作，来完成carry + tmp。
当carry为0，也就是没有进位的时候，carry + tmp = tmp，此时就可以退出循环，得到最终结果了。
当b = 0，那么就是carry = 0，此时最终结果就是tmp，由于最后我们会把tmp赋值给a，所以return a。
数字查找
LeetCode 136. 只出现一次的数字
本题要求我们在一堆数字中，找到只出现一次的数字，对于这种在一堆数字中查找出现次数比较特殊的题型，都可以优先考虑用位运算。
这种题型，都要用到异或的运算率：
a ^ a = 0;
a ^ 0 = a;
a ^ b ^ c = (a ^ b) ^ c;
以上运算率中，可以提取出一个重要信息：将一堆数字异或在一起，出现偶数次的数字，会变成0。最后变成所有出现次数为奇数的数字互相异或。
比如：a ^ b ^ b = a ，因为a出现一次，为奇数次，b出现两次，为偶数次，最后两个b抵消，变成a ^ 0，也就是a。
再比如：c ^ a ^ b ^ b ^ c ^ c = a ^ c，因为a和c都是出现了奇数次，b出现了偶数次，最后就只剩下a和c进行异或。
而对于本题来说，我们要求的数字只出现一次，为奇数次；其他数字都出现两次，为偶数次。我们只需要遍历数组，把所有值异或起来，除了目标值以外的值都被抵消掉了，最后结果就是目标值。
代码：
class Solution
{
public:
int singleNumber(vector<int>& nums)
{
int ret = 0;
for (auto& e : nums) // 遍历数组
ret ^= e;
return ret;
}
};
LeetCode 260. 只出现一次的数字 III
本题中有两个数字只出现了一次，其他数字都出现了两次。
与之前思路一样，假设我们要求的目标值为a和b，把所有值都异或起来，结果就是a ^ b。
那么问题就来了，我们要如何从a ^ b中拆分出a和b呢？
按位异或的规则为：相同为0，相异为1，也就是说a ^ b中为1的地方，就是a与b不同的位，我们可以通过这个位来区分两者。
假设我们求出了，a ^ b的第x位为1，那么整个数组的数据就可以拆分为两份：第x位为1，第x位为0。而a和b就分别在这两份中。假设a在第一份元素中，b在第二份元素中。
第x位为1：a+ 其它第x位为1
第x位为0：b+ 其它第x位为0
因为除了a和b，其他数字都出现两次，相同的数字第x位也相同，会被分到同一份中。
因此第一份数据中，除了a以外，其他数字都出现两次；第二份数据中，除了b以外，其他数字也出现两次。
我们将第一份数据中所有元素异或起来，得到的就是a，第二份数据中的所有元素异或起来，得到的就是b。
逻辑：
- 先把整个数组按位异或，得到
a ^ b- 找出
a ^ b中，任意一个为1的位- 根据这个位把数组划分为两份
- 每一份中分别按位异或，得到的结果就分别是
a和b
代码：
class Solution
{
public:
vector<int> singleNumber(vector<int>& nums)
{
int tmp = 0;
for (auto& e : nums) // 按位异或整个数组
tmp ^= e;
vector<int> ret = { tmp, tmp };
int x = (tmp == INT_MIN) ? tmp : tmp & (-tmp); // 得到a ^ b 中的一位1
for (auto& e : nums) // 遍历数组
{
if (e & x) // 第一份数据，第x位为1
ret[0] ^= e;
else // 第二份数据，第x位为0
ret[1] ^= e;
}
return ret;
}
};
这里我额外说明一句代码：
int x = (tmp == INT_MIN) ? tmp : tmp & (-tmp); // 得到a ^ b 中的一位1
其目的在于，得到a ^ b中的最右侧的一位1，也就是tmp & -tmp，并赋值给x。但是如果tmp的值是int类型的最小值，其二进制就是：
10000000 00000000 00000000 00000000
也就是，除了第一位，其它位都是0，此时-tmp是超过了int的存储范围的，会发生进位。
其取反，+1后为：
11111111 11111111 11111111 11111111 //取反
1 00000000 00000000 00000000 00000000 //+1
可以看出来发生了越界。
而我们的目的只是为了提取tmp最右侧的一个1，如果tmp是INT_MIN，本身就只有一个1，因此不用额外提取，直接x = tmp即可。
LeetCode 137. 只出现一次的数字 II
本题中，目标元素出现一次，其它元素出现三次，都是奇数次，那么我们就不能用异或来区分它们了。
这种情况下，就要用位图的思想，来单独统计每一个位的情况。
因为输入的数据是int类型，那么就固定只有32个位，对于每个位，我们都单独统计。
创建一个32个元素的整型数组bitmap，每个元素代表一个比特位。
遍历数组，对于每个元素，将其所有位的值加进bitmap中。
比如某个元素第0位是1，那么bitmap[0] += 1，第1位为0，那么bitmapp[1] += 0，以此类推，直到第31位。每个元素都执行一次该操作。
最后bitmap数组中，就统计到了对应位上出现的1个数。由于其它元素都出现了三次，对于每一位数据，都是3的倍数 + 目标值在该位的值0/1
那么bitmap[i] % 3就可以还原出目标元素第i位是0还是1。
代码逻辑：
- 创建一个
bitmap数组，存储每一位上的1的个数- 遍历数字，把每一个元素的比特位加到
bitmap中bitmap中每个元素都%3得到原始数据，此时整个数组都由1和0组成，也就是目标元素的二进制值
代码：
class Solution
{
public:
int singleNumber(vector<int>& nums)
{
vector<int> bitmap(32);
int ret = 0;
for (auto& e : nums) // 遍历数组
{
for (int i = 0; i < 32; i++) // 遍历每个元素的32个比特位
{
bitmap[i] += (e >> i) & 1; // 将第i位数据，加到bitmap的第i个元素中
}
}
for (int i = 0; i < 32; i++) // 遍历bitmap
{
ret |= (bitmap[i] % 3) << i; // %3还原出目标元素的二进制
}
return ret;
}
};
总结
常见运算：
&：按位与
|：按位或
~：按位取反
^：按位异或
<<：左移操作符
>>：右移操作符
给一个数
n，求它二进制的第x位是0还是1
(n >> x) & 1
给一个数
n，将它二进制的第x位修改为1
n |= 1 << x;
给一个数
n，将它二进制的第x位修改为0
n &= ~(1 << x);
给一个数
n，提取它最右侧的1
n & -n;
给一个数
n，把它最右侧的1变为0
n & (n - 1);
异或运算率
a ^ a = 0;
a ^ 0 = a;
a ^ b ^ c = (a ^ b) ^ c;
模拟加法：
按位异或^可以视为无进位加法，而(a & b) << 1可以求出进位，两者配合可以模拟加法操作。
查找数字
-
如果目标元素与其它元素奇偶性不同，通过异或的运算律求解；如果目标值有两个，利用按位异或的特性找出两个目标元素不同的位，然后利用这个位把数组划分为两份，再进行分别查找
-
如果目标元素与其它元素奇偶性相同，利用位图思想，把每个比特位的
1的个数求出来，然后想办法利用%来消除其它元素的影响，最后位图中只留下目标元素的二进制值
