【优选算法 & 位运算】位运算算法入门详解：常见位运算总结
判定字符是否唯一
题目解析
算法原理
解法一 ：哈希数组
从前往后扫描字符串，把扫描到的字符先进行判断，如果对应的 val = 0 ，则放入哈希表中，否则返回 false，知道扫描完整个字符；时间复杂度为 O(N），空间复杂度 O(N)；
我们不需要真的创建哈希表，只需要创建一个大小为26 的哈希数组，只要遍历到的元素，对应到的哈希元素+1；
解法二 ： 借助位图的思想
单独一个 int 变量有32位：
从 0 位到 25位分别代表从 a~z 26个小写字母，只要前面出现过，只要遍历到字符，对应的比特位就是1 ，否则为0；这里大量运用查询某一个比特位是否为1 ，以及将某一个比特位修改为1；
优化：鸽巢（抽屉）原理
【优选算法 — 双指针】双指针小专题，在这篇博客的证明快乐数成环有讲解鸽巢原理
因为这道题有26个英文字母，当这个字符串长度 len > 26，就一定有重复字符；所以我们可以先判断字符串长度是否大于26；
编写代码
解法一 ：哈希数组
解法二 ： 借助位图的思想
丢失的数字
题目解析
算法原理
解法一 ：哈希表
因为要在 n+1 个数中找丢失的数，所以我们可以创建同等规模的哈希表，哈希表的key为 0到 n 这n+1个元素，在扫描一遍数组之后，返回 val=0 对应的key；时间复杂度O(N)， 空间复杂度 O(N)
解法二 ： 高斯/等差数列求和
时间复杂度O(N)， 空间复杂度 O(1)
解法三 ： 位运算（异或^运算的运算律）
我们把这一堆数（上下所有的数）全部异或在一起，所有数异或在一起，相同的数会消消乐，最终结果就是缺失的数；时间复杂度为O(N)，空间复杂度O(1)
编写代码
解法一 ：哈希表
解法二 ： 高斯/等差数列求和
解法三 ： 位运算（异或^运算的运算律）
为了方便理解两步循环的异或操作，我们简单举一个例子：
假设第一个循环是ret=1^2^3^5，第二个循环是ret=ret^1^2^3^4^5，那么通过异或的消消乐原理，最终计算的就是ret=1^1^2^2^3^3^4^5^5=4
两整数之和
题目解析
算法原理
解法 ： 使用位运算（异或无进位相加）
因为异或使用的是无进位相加；
所以接下来，我们需要把没有进位的位置找到：
- 对于上图，如果两个数的同一位置进行相加，那么进位的结果只可能是1或者0；
- 我们再整体来看这三行数据，发现蓝色的两行，通过按位与&，就可以得到下面红色的结果；
所以接下来，我们只需要找到异或中的被消去的进位即可；
将这两行对应位的数字进行 按位与& 操作，即可找到异或中的被消去的进位；
但是需要注意的是，我们得到的进位，是进到&出结果的进一位：
所以我们算出 a&b 的结果之后，要把结果<<1：
在求出进位之后，我们需要判断当前得到的 c^d 的过程是否还会有消去进位的情况：
如果还是存在消去进位的情况，我们就要重复上面的操作，先分别算出 c^d 和 (c&d)<<1 的结果；
继续 e^f ，此时就没有消去进位的情况，得到的就是最终的结果：
我们只需要以 (a&b)<<1 != 0 作为循环判断条件，对每次得到的进位结果进行判断，直到进位等于0，结束循环，最终的 a^b 即为最开始 a+b 的结果；
过程总结
编写代码
只出现一次的数字Ⅱ
题目解析
算法原理
这道题的特点是，其中一个数出现一次，剩余所有的数出现三次；下图表示一个 int 类型的32位比特位：
任意一个比特位，会出现如下四种情况：
对四个数的32位比特位的某一位之和出现的四种情况进行剖析：
我们发现，圈起来的数字，前后一 一对应 ；左边圈起来的数，表示只出现一次的那一个比特位，这个比特位，与四个比特位之和%3得到的结果相等；
因此，我们创建一个返回值 ret，把这四个数的每一个比特位加起来，再模3，得到的结果放入 ret 对应的比特位上；
如果模3的结果为0，不用修改 ret 对应的比特位，如果模3 的结果为1 ，就把 ret 对应比特位修改为1 ，直到修改完 ret 的32位比特位即可；
拓展：如果一个数组中，有一个数出现一次，其他相同的数出现 n 次，我们的把模3修改成模n ，其他操作相同；
编写代码
消失的两个数字
题目解析
算法原理
这道题的算法原理是丢失的数字+只出现一次的数字Ⅲ（不是Ⅱ）两个题的算法原理糅合在一起；
解法：位运算
我们回忆丢失的数字中的算法原理，就是把 nums 中的数和 0 ~ N 这所有的数都糅合在一起，通过异或来找出丢失的数，那么类比这道题：
将所有的数异或在一起，这些异或在一起的数，我们定义一个变量 tmp 来接收：
而通过异或消消乐的特性，最终 tmp = a ^ b，就是缺失的那两个数异或的结果；
接下来，我们要把 a ，b 分开，我们需要先找到 tmp 中，比特位为1 的那一位；为什么要找这一位呢？
因为 a 和 b 一定是不同的两个数， a^ b 的最终结果 tmp 绝对是不等于 0 的 ，所以在 tmp 的32位比特位上，肯定有二进制数为 1 的比特位，我们记录这个位置的下标为 x :
这个二进制数 1 的出现，是因为异或运算律：相同为0 ，相异为1，所以只要 tmp 中二进制位对应的二进制数为1，a ，b 对应的二进制位肯定是不同的；
那么，我们就可以根据 x 位的不同，对 a，b 划分成两个单独部分，对每个部分中的所有数进行异或：
思考链路
总结
编写代码
原文地址：https://blog.csdn.net/2402_84916296/article/details/144338751
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！