位运算的总结
基础位运算
<< 左移 >> 右移 ~ 按位取反
& 按位与：有0则0 | 按位或：有1则1 ^ 按位异或：相同为0，相异为1/无进位相加
位运算的优先级：不需要记，根据自己的要求加上括号
给一个数n，确定它的二进制表示中的第 x 位是 0 还是 1
如果要将0移动到最低位，应该向右移动2位，也就是下标位
那么如何确定第x位是0还是1，将 n 向右移动 x 位，在&1，根据&运算的规则：有0则0，同1则1。若第x位是0，0&1=0；若第x位是1，1&1=1。公式表示为：(n >> x) & 1
将一个数 n 的二进制表示的第 x 位修改成 1
假设要将0修改成1，仅需将0 | 1即可，根据 | 运算规则：有1则1，同0则0。如何让指定比特位的0 | 1呢？将1左移x位，与n按位或即可。1数字的其它比特位都是0，n的其它比特位与0异或不会被改变。公式表示：n |= (1 << x)
将一个数 n 的二进制表示的第 x 位修改成0
假设要将1修改成0，但是不影响 n 的其它比特位，应该怎么办？让修改位按位与0，其它位按位与1即可。怎么获取到这么一个数：11…………0111？仅需将1左移 x 位，再取反即可，即 ~(1 << x)。公式：n &= ~(1 << x)
位图思想
位图思想本质就是 hash 表，只是我们见到的 hash 表大多都是数组，使用一个变量的二进制位来记录信息。比特位为0/1各自表示一种信息。位图离不开上述提到的三种操作。
提取一个数 n 的二进制表示中最右侧的 1
仅需将 n & -n即可，-n 的二进制表示是 ~n + 1
~n:1001010111；~n+1:1001011000。将 1001011000 与 n 的二进制表示一对比发现以最右侧的1为分界点，右侧没有改变，左边取反。那么将 n & ~n，&运算规则：有0则0，同1则1。以最右侧的1的左边都是相反的，那么&后都为0，因此&后，最右侧的1就被提取出来了。公式：n & -n
将一个数 n 的二进制表示中最右侧的 1 变成 0
公式：n & (n-1)
n： 0110101000 n-1：0110100111
n – 1 操作就是将以最右侧的 1 为分界点，右侧取反（包含分界点1），左侧不改变。
此时 n-1 & n，&运算规则：有0则0，同1则1。n-1 & n = 0110100000，这样就将最右侧的1变成0了
异或运算的运算律
a ^ 0 = a a ^ a = 0 a ^ b ^ c = a ^ (b ^ c)
算法题目
题目1：191. 位1的个数 - 力扣（LeetCode）
题目分析
给定一个正整数
n，编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中 设置位 的个数（也被称为汉明重量）。
题目示例
示例 1：
输入：n = 11输出：3解释：输入的二进制串1011中，共有 3 个设置位。示例 2：
输入：n = 128输出：1解释：输入的二进制串10000000中，共有 1 个设置位。示例 3：
输入：n = 2147483645输出：30解释：输入的二进制串1111111111111111111111111111101中，共有 30 个设置位。
算法原理
题目要求找 n 二进制表示中 1 的个数，转化思路，也就是 n 的二进制表示中能有几个 1 变成 0，即n &= (n-1)，有几个1，n &= (n-1)就可以执行几次。
代码实现
class Solution { public: int hammingWeight(int n) { // 计数器 int count = 0; while(n) { // 将1变成0,有几个1就循环几次 n &= (n - 1); count++; } return count; } };题目2：338. 比特位计数 - 力扣（LeetCode）
题目分析
给你一个整数
n，对于0 <= i <= n中的每个i，计算其二进制表示中1的个数，返回一个长度为n + 1的数组ans作为答案。
题目示例
示例 1：
输入：n = 2输出：[0,1,1]解释：0 --> 0 1 --> 1 2 --> 10示例 2：
输入：n = 5输出：[0,1,1,2,1,2]解释：0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101
算法原理
这道题和上一道题一样，只不过这道题要循环统计 [0,n] 中每个数的二进制表示 1 的个数。
代码实现
class Solution { public: vector<int> countBits(int n) { // 返回值 vector<int> ret(n + 1); for(int i = 0; i <= n; i++) { // 统计i中1的个数 int count = 0; int k = i; while(k) { k &= (k-1); count++; } ret[i] = count; } return ret; } };题目3：461. 汉明距离 - 力扣（LeetCode）
题目分析
两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
给你两个整数
x和y，计算并返回它们之间的汉明距离。
题目示例
示例 1：
输入：x = 1, y = 4输出：2解释：1 (0 0 0 1) 4 (0 1 0 0) ↑ ↑ 上面的箭头指出了对应二进制位不同的位置。示例 2：
输入：x = 3, y = 1输出：1
算法原理
先将两个数的二进制表示存储起来，在依次比较相同的比特位上的元素是否相等。如何获取一个数的二进制表示的 x 位比特位？(n >> x) & 1。
代码实现
class Solution { public: int hammingDistance(int x, int y) { int arr1[32] = { 0 }; int arr2[32] = { 0 }; // 将 x,y 的二进制位存储起来 for(int i = 0; i < 32; i++) { // 获取x,y的每一个二进制位 arr1[i] = (x >> i) & 1; arr2[i] = (y >> i) & 1; } // 计数器 int count = 0; // 比较不同 for(int i = 0; i < 32; i++) { if(arr1[i] != arr2[i]) { count++; } } return count; } };题目4：136. 只出现一次的数字 - 力扣（LeetCode）
题目分析
给你一个非空整数数组
nums，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
题目示例
示例 1 ：
输入：nums = [2,2,1]
输出：1
示例 2 ：
输入：nums = [4,1,2,1,2]
输出：4
示例 3 ：
输入：nums = [1]
输出：1
算法原理
使用异或运算的规则，a^a = 0，0^a = a。将 nums 数组中所有的元素异或在一起，最终的结果就是数组中只出现一次的数字。
代码实现
class Solution { public: int singleNumber(vector<int>& nums) { int ret = 0; for(auto e : nums) { ret ^= e; } return ret; } };题目5：260. 只出现一次的数字 III - 力扣（LeetCode）
题目分析
给你一个整数数组
nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按任意顺序返回答案。你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。
"线性时间复杂度"说明时间复杂度为O(N)，"只使用常量额外空间"说明空间复杂度为O(1)。
题目示例
示例 1：
输入：nums = [1,2,1,3,2,5]输出：[3,5]解释：[5, 3] 也是有效的答案。示例 2：
输入：nums = [-1,0]输出：[-1,0]示例 3：
输入：nums = [0,1]输出：[1,0]
算法原理
本道题和上一道题的思路一致，但是这道题nums数组中有两个只出现一次的数字，因此我们需要将nums数组分成两部分，每一部分都有一个只出现一次的数字。分组的依据的是什么？根据nums数字所有元素异或得到结果 all，获取all的二进制表示中最右边为1的比特位 bitmap，让 bitmap 与 nums 中元素按位与，为 1 的分成一组，为 0 的分成一组。
代码实现
class Solution { public: vector<int> singleNumber(vector<int>& nums) { // long 类型防止溢出 long all = 0; for(auto e : nums) { all ^= e; } // 获取all中的最低位的1，即最右边比特位为1 // long 类型防止溢出 long lowbit = all & (-all); // 分组 int nums1 = 0, nums2 = 0; for(auto e : nums) { // 在分组的过程中就开始异或 if(e & lowbit) { nums1 ^= e; } else { nums2 ^= e; } } return {nums1, nums2}; } };题目6：面试题 01.01. 判定字符是否唯一 - 力扣（LeetCode）
题目分析
实现一个算法，确定一个字符串
s的所有字符是否全都不同。
题目示例
示例 1：
输入:s= "leetcode"输出:false示例 2：
输入:s= "abc"输出:true
限制：
0 <= len(s) <= 100s[i]仅包含小写字母- 如果你不使用额外的数据结构，会很加分。
算法原理
解法1：hash表
遍历字符串，判断遍历到的字符是否存在 hash 表中，如果不存在，则加入hash表，继续向后遍历；如果存在，直接返回 false。
解法2：位图
单独的 int 变量就有32位比特位，从右向左依次表示 a,b,c,……。仅需使用 0~25 位比特位就可以表示26个英文字母了。其中 0 表示没有出现过，1 表示出现过，使用位图思想来替代数据结构hash。主要操作是查询某位比特位是否为1和将某个比特位修改成1。
优化点：根据双指针算法处提到的鸽巢原理，一个有26个英文字母，如果字符串的长度大于26，那么字符串中一定存在相同的字符。
代码实现
class Solution { public: bool isUnique(string astr) { // 求字符串的长度 int len = astr.length(); // 小优化 if(len > 26) { return false; } // 使用位图思想 int bitmap = 0; for(auto ch : astr) { int index = ch - 'a'; // 判断第 index 位是否为 1，即是否存在 // 存在，返回false if(((bitmap >> index) & 1) == 1) { return false; } // 不存在，将第index比特位变成1 bitmap |= (1 << index); } return true; } };题目7：268. 丢失的数字 - 力扣（LeetCode）
题目分析
给定一个包含
[0, n]中n个数的数组nums，找出[0, n]这个范围内没有出现在数组中的那个数。
题目示例
示例 1：
输入：nums = [3,0,1]
输出：2
解释：
n = 3，因为有 3 个数字，所以所有的数字都在范围[0,3]内。2 是丢失的数字，因为它没有出现在nums中。示例 2：
输入：nums = [0,1]
输出：2
解释：
n = 2，因为有 2 个数字，所以所有的数字都在范围[0,2]内。2 是丢失的数字，因为它没有出现在nums中。示例 3：
输入：nums = [9,6,4,2,3,5,7,0,1]
输出：8
解释：
n = 9，因为有 9 个数字，所以所有的数字都在范围[0,9]内。8 是丢失的数字，因为它没有出现在nums中。
提示：
n == nums.length1 <= n <= 1040 <= nums[i] <= nnums中的所有数字都独一无二
算法原理
解法1：hash表
创建一个 n + 1大小的hash表，遍历 nums 数组，将 nums 中的元素加入到hash表中，最终看哪个位置的元素个数为0，那么那个下标就是目标值。
解法2：求和
使用等差数列的求和公式计算出从0~n的和，再依次减去整个nums的元素和，最终的结果就是目标值。
解法3：利用位运算
创建一个 n + 1大小的数组，将创建的数组与 num s数组全部异或在一起，最终结果就是目标值。
使用第三种解法来解决问题。
代码实现
class Solution { public: int missingNumber(vector<int>& nums) { // 返回值 int ret = 0; // 将 nums 数组中的元素异或在一起 for(auto e : nums) { ret ^= e; } // 再将ret与[0,n]异或 for(int i = 0; i <= nums.size(); i++) { ret ^= i; } return ret; } };题目8：371. 两整数之和 - 力扣（LeetCode）
题目分析
给你两个整数
a和b，不使用运算符+和-，计算并返回两整数之和。
题目示例
示例 1：
输入：a = 1, b = 2输出：3示例 2：
输入：a = 2, b = 3输出：5
算法原理
题目要求不能使用加法和减法，大概率就是使用位运算。这里使用异或运算，在前文提到过，异或运算规则：无进位相加。找到异或运算的进位即可。
例：13 + 28 = 41，无进位相加的结果：
要找到进位，需要思考什么时候会出现进位。当1^1时，才会进位，即1,1是1，1,0和0,1是0，这不就是 & 运算吗？因此找进位的时候，a&b。
但是我们找到只是会进位的位置，进位是向左进位的，因此 a&b 再左移一位即可。
接下来再重复上面的操作，即将 a^b 看作 a，(a&b)<<1 看作 b。
最终的进位仍然存在，因此还需要重复的操作。
最终进位变成0，即b == 0时终止操作。
因此使用位运算作加法运算，不断重复a^b 和 a&b<<1。
代码实现
class Solution { public: int getSum(int a, int b) { // 进位 a&b<<1 如果不等于0，就一直需要重复 // (a ^ b)操作和(a&b << 1)操作 while(b != 0) { int c = a ^ b; // 无进位结果 int d = (a & b) << 1; // 进位 a = c; b = d; } // 最终结果就是a return a; } };题目9：137. 只出现一次的数字 II - 力扣（LeetCode）
题目分析
给你一个整数数组
nums，除某个元素仅出现一次外，其余每个元素都恰出现三次 。请你找出并返回那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
题目示例
示例 1：
输入：nums = [2,2,3,2]输出：3示例 2：
输入：nums = [0,1,0,1,0,1,99]输出：99
算法原理
使用位图来解决这道问题。
nums数组中每一个元素都是整型，所有元素的任意比特位之和可能出现以下四种情况：3n 个0+0，3n 个0+1，3n 个1+0，3n 个1+1
第n位比特位之和为 3n 个0+0，那么第 n 位比特位的总和是：0
第n位比特位之和为 3n 个0+1，那么第 n 位比特位的总和是：1
第n位比特位之和为 3n 个1+0，那么第 n 位比特位的总和是：3n
第n位比特位之和位 3n 个1+1，那么第 n 位比特位的总和是：3n+1
再将这些比特位总和%3，则
3n个0+0 -> 0 % 3 = 0
3n个0+1 -> 1 % 3 = 1
3n个1+0 -> 3n % 3 = 0
3n个1+1 -> 1 % 3 = 1
%3后的结果与前面的结果相呼应，3n 后面加的数字是只出现一次的数的比特位。
如果只出现一次的数的比特位为 0，那么所有比特位加起来模3仍然等于0
如果只出现一次的数的比特位为 1，那么所有比特位加起来模3仍然等于1
具体步骤：将 nums 数组中所有元素的第 i 位加起来再模上3，如果为0，那么返回值 ret 的第 i 位比特位不变，如果为1，那么返回值 ret 的第 i 位比特位变成1。
题目再继续扩展，如果一个数只出现一次，其余数出现了 k 次，那么模的就是 k。
代码实现
class Solution { public: int singleNumber(vector<int>& nums) { // 返回值 int ret = 0; // 依次修改ret的每一位比特位 for(int i = 0; i < 32; i++) { // 记录nums数组的所有元素的第i位比特位之和 int sum = 0; for(auto e : nums) { // 获取 e 的第i位比特位 sum += ((e >> i) & 1); } // 若 sum % 3 == 1,ret的第i位比特位变成1 if(sum % 3 == 1) { ret |= (1 << i); } } return ret; } };题目10：面试题 17.19. 消失的两个数字 - 力扣（LeetCode）
题目分析
给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
以任意顺序返回这两个数字均可。
题目示例
示例 1：
输入：[1]输出：[2,3]示例 2：
输入：[2,3]输出：[1,4]
算法分析
这道题可以转换成《只出现一次的数字III》+《丢失的数字》，即找到 nums 数组和 1~n+2 序列中只出现一次的数字，将 nums 数组和 1~n+2 序列看成一个整体，那么这道题就转化成了在这个整体中只出现一次的两个数字。
在解决《只出现一次的数字III》问题中，将 nums 所有的元素都异或在一起，接着再根据 bitmap 变量进行分组，bitmap 就是异或结果中最右边为1的比特位。为什么要根据它来作为分组条件？整体中的元素与 bitmap 异或的结果只有两种 1 和 0，如此就可以将整体序列分成两组。这两组异或的结果就是返回值。
代码实现
class Solution { public: vector<int> missingTwo(vector<int>& nums) { // 整体序列的异或结果 long all = 0; for(auto e : nums) { all ^= e; } for(int i = 1; i <= nums.size() + 2; i++) { all ^= i; } // 获取bitmap,即all中最右边为1的比特位 long bitmap = all & (-all); // 分组 int nums1 = 0, nums2 = 0; for(auto e : nums) { if(e & bitmap) { nums1 ^= e; } else { nums2 ^= e; } } for(int i = 1; i <= nums.size() + 2; i++) { if(i & bitmap) { nums1 ^= i; } else { nums2 ^= i; } } return {nums1, nums2}; } };
