使用位操作高效解决单个元素出现问题【位运算】

本文主要是介绍使用位操作高效解决单个元素出现问题【位运算】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

使用位操作高效解决单个元素出现问题

在日常的算法面试和编程挑战中，常常会遇到寻找单个出现元素的问题。尽管可以用哈希表（map）轻松解决，但要求更高效的线性时间复杂度和常量空间复杂度时，位操作特别是异或（XOR）运算提供了一个巧妙的解决方案。本篇博客将深入探讨这个问题，详细解释异或运算的特性，并展示其在解决该类问题中的强大作用。

问题描述：

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找到那个只出现了一次的元素。

示例：

输入: nums = [4,1,2,1,2]
输出: 4

136. 只出现一次的数字 - 力扣（LeetCode）

常规解法：使用 `map` 记录次数

最初，我们可能会想到使用一个哈希表来记录每个元素的出现次数，然后遍历哈希表找到那个只出现一次的元素。具体步骤如下：

创建一个哈希表，遍历数组并记录每个元素的出现次数。
再次遍历哈希表，找到只出现一次的元素并返回。

这种方法虽然直观且易于理解，但由于需要额外的存储空间来保存元素的出现次数，空间复杂度为 (O(n))。

代码实现：

#include <iostream>
#include <vector>
#include <unordered_map>using namespace std;class Solution {
public:int singleNumber(vector<int>& nums) {unordered_map<int, int> countMap;for (int num : nums) {countMap[num]++;}for (auto& entry : countMap) {if (entry.second == 1) {return entry.first;}}return -1;  // Ideally, this line should never be reached.}
};int main() {Solution sol;vector<int> nums = {4, 1, 2, 1, 2};cout << "The single number is: " << sol.singleNumber(nums) << endl;return 0;
}

分析：

时间复杂度：由于我们遍历了数组两次，因此时间复杂度为 (O(n))。
空间复杂度：需要 (O(n)) 的额外空间来存储哈希表。

尽管这种方法解决了问题，但它不符合题目要求的常量空间复杂度。为此，我们需要寻找更高效的解决方案。

高效解法：使用异或运算

异或运算的性质：

交换律：a ^ b = b ^ a
结合律：a ^ (b ^ c) = (a ^ b) ^ c
任何数与0异或等于它本身：a ^ 0 = a
任何数与自己异或等于0：a ^ a = 0

基于这些性质，我们可以推导出一个重要结论：如果对数组中所有的元素进行异或运算，那么出现两次的元素都会相互抵消，最终的结果就是那个只出现了一次的元素。

具体步骤：

初始化一个变量 res 为0。
遍历整个数组，将每个元素与 res 进行异或运算。
遍历结束后，res 中存储的就是那个只出现了一次的元素。

代码实现：

#include <iostream>
#include <vector>using namespace std;class Solution {
public:int singleNumber(vector<int>& nums) {int res = 0;for (int num : nums) {res ^= num;  // 进行异或运算}return res;}
};int main() {Solution sol;vector<int> nums = {4, 1, 2, 1, 2};cout << "The single number is: " << sol.singleNumber(nums) << endl;return 0;
}

详细解释：

设 nums = [4, 1, 2, 1, 2]，初始 res = 0。
遍历数组并依次异或每个元素：
- res = 0 ^ 4 = 4

    0000
^ 0100
_______0100

res = 4 ^ 1 = 5

   0100
^ 0001
_______0101

res = 5 ^ 2 = 7

   0101
^ 0010
_______0111

res = 7 ^ 1 = 6

   0111
^ 0001
_______0110

res = 6 ^ 2 = 4

   0110
^ 0010
_______0100

最终结果 res = 4，即那个只出现了一次的元素。

性能分析：

时间复杂度：
由于我们只遍历了一次数组，所以时间复杂度为 (O(n))，与使用哈希表的方法相同。

空间复杂度：
我们只使用了一个额外的变量 res，所以空间复杂度为 (O(1))，这比哈希表的方法更优。

异或运算在其他场景中的应用：

异或运算不仅在寻找单个出现元素的问题中有应用，还可以用于以下场景：

1. 交换两个变量的值

在C++或其他支持按位运算的语言中，可以使用异或运算来在没有额外存储空间的情况下交换两个变量的值。这是因为对于任何数字 a 和 b，有以下性质：

a ^ b ^ b = a （两次异或同一个数等于原数）
a ^ a = 0 （任何数与自己异或等于0）

基于这两个性质，可以编写如下代码来交换两个变量 a 和 b：

void swapWithoutTemp(int &a, int &b) {a = a ^ b;  // a现在存储的是a^bb = a ^ b;  // b现在存储的是a (因为a^b^b=a)a = a ^ b;  // a现在存储的是b (因为a^b^a=b)
}

2. 检测两个数的不同位

异或运算可以帮助我们找到两个整数之间不同的二进制位。如果两个位相同，则异或结果为0；如果不同，则结果为1。因此，通过异或运算，我们可以很容易地找出两个数的二进制表示中哪些位不同。

bool bitsDiffer(int a, int b) {int diff = a ^ b;while (diff != 0) {if (diff & 1) {// 当前位不同std::cout << "Bit differs at position: " << 31 - __builtin_clz(diff) << std::endl;}diff >>= 1;}
}

这里使用了__builtin_clz函数来找到最高位1的位置，并计算出具体哪一位不同。__builtin_clz返回的是从左边开始第一个非零位的位置，所以需要减去这个值以得到具体的位位置。

3. 求两个数的汉明距离

汉明距离是指两个字符串或数字的二进制表示中对应位不同的数量。使用异或运算，然后计算结果中1的个数，就可以得到汉明距离。

int hammingDistance(int x, int y) {int xorResult = x ^ y;int distance = 0;while (xorResult) {distance += xorResult & 1; // 如果最低位为1，则增加距离xorResult >>= 1; // 移除最低位}return distance;
}