【算法系列篇】位运算-1：https://developer.aliyun.com/article/1430520
4. 只出现一次的数字
https://leetcode.cn/problems/single-number-ii/
4.1 题目要求
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
示例 1：
输入：nums = [2,2,3,2] 输出：3
示例 2：
输入：nums = [0,1,0,1,0,1,99] 输出：99
提示：
- 1 <= nums.length <= 3 * 104
- -231 <= nums[i] <= 231 - 1
- nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次
class Solution { public int singleNumber(int[] nums) { } }
4.2 做题思路
通过题目，我们可以知道，除了那个只出现了一次的数字之外，其他的数字都出现了一次，所以呢，我们可以将数组中的每个元素的32个比特位分别相加，将结果 % 3，就会得到那个只出现一次的数字的对应比特位。
4.3 Java代码实现
class Solution { public int singleNumber(int[] nums) { int ret = 0; for(int i = 0; i < 32; i++) { int tmp = 0; for(int n : nums) { tmp += (n >> i) & 1; } ret |= (tmp % 3) << i; } return ret; } }
5. 消失的两个数字
https://leetcode.cn/problems/missing-two-lcci/
5.1 题目要求
给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
以任意顺序返回这两个数字均可。
示例 1:
输入: [1] 输出: [2,3]
示例 2:
输入: [2,3] 输出: [1,4]
提示：
- nums.length <= 30000
class Solution { public int[] missingTwo(int[] nums) { } }
5.2 做题思路
这个题目跟上面的消失的一个数字其实是类似的，只不过这里出现了两个消失的数字，我们不可能一次就找到两个消失的数字，但是我们可以分两次找。可以将这道题目转换为数组中只出现了一次的数字，这里大家可以看看我之前写过的一篇文章寻找单身狗，但是呢一个数组中只能找到一个只出现了一次的数字，如果要想找到两个只出现了一次的数字，我们可以将这两个消失的数组分别给分到两个不同的数组中，然后在每一个数组中找那个只出现了一次的数字，最终这两个消失的数字都会被找到。那么，如何将这两个消失的数字分在两个不同的数组中呢？同样是将原本的数组和现有的数组中的所有元素都进行异或操作，相同的元素异或为0，最后剩下的其实就是这两个消失的数字异或的结果，然后我们需要在这个异或的结果中找到比特位为 1 的位置，因为异或，相异为 1 ，相同为0，当找到这个为 1 的比特位之后，就可以将这些元素进行分组了，该比特位为 1 的为一组，为 0 的为另一组。
5.3 Java代码实现
class Solution { public int[] missingTwo(int[] nums) { int[] ret = new int[2]; int tmp = 0; for(int n : nums) tmp ^= n; for(int i = 1; i <= nums.length + 2; i++) tmp ^= i; int flg = 0; //用来记录异或结果比特位为1的位置 for(int i = 0; i < 32; i++) { if(((tmp >> i) & 1) == 1) { flg = i; break; } } for(int n : nums) { if(((n >> flg) & 1) == 1) ret[0] ^= n; else ret[1] ^= n; } for(int i = 1; i <= nums.length + 2; i++) { if(((i >> flg) & 1) == 1) ret[0] ^= i; else ret[1] ^= i; } return ret; } }
总结
通过本篇博客，我们深入了解了位运算算法及其在计算机领域中的重要性和应用。位运算算法是一项强大的工具，它基于二进制位的操作，能够高效地处理二进制数据，提升程序的性能和效率。
在实际应用中，我们可以利用位运算算法来实现各种位级别的操作，如位掩码、位操作、整数运算优化、位图算法和压缩算法等。这些算法和技巧可以在底层系统编程、嵌入式系统、网络协议和算法优化等领域发挥重要作用。
然而，在使用位运算算法时，也需要注意一些优化技巧和注意事项。我们需要注意位运算的优先级、位移操作的性能和溢出问题，以及如何利用位运算进行快速乘法、除法和判断奇偶性等操作。深入理解这些技巧，能够更好地应用位运算算法，提高代码的效率和准确性。
位运算算法是计算机科学中一个广泛应用的领域，通过深入学习和实践，我们可以进一步探索和发现更多有趣的位运算技巧和应用。在日常编程中，合理运用位运算算法，能够帮助我们解决一些复杂的问题，实现更高效和可靠的程序。
希望本篇博客能够为读者提供一个全面而清晰的位运算算法入门指南，让大家对位运算算法有更深入的了解，并能够应用于实际开发中。通过不断学习和探索，我们可以进一步提升自己的编程能力，并在算法领域中取得更多的成就。
感谢您的阅读，希望本篇博客对您有所帮助。如果您有任何问题或反馈，欢迎留言交流。祝愿您在位运算算法的学习和应用中取得成功！
