10.03_按位异或
按位异或
问题描述
按位异或运算(^)是一种基本的位运算，当两个位不同时结果为1，相同时为0。常用于数字加密、交换数字等场景。
性质：任何数异或自身等于0，当x,y为正整数时，abs(x-y)<=x^y<=x+y。
基本操作
算法思想
- 两个位不同时结果为1
- 可用于无临时变量交换
- 适用于成对数字查找
- 时间复杂度
代码实现
class Solution {
public:
// 交换两个数
void swap(int& a, int& b) {
a ^= b;
b ^= a;
a ^= b;
}
// 查找只出现一次的数
int findSingle(vector<int>& nums) {
int result = 0;
for (int num : nums) {
result ^= num;
}
return result;
}
// 判断两个数是否相等
bool isEqual(int a, int b) {
return (a ^ b) == 0;
}
// 翻转特定位
int flipBit(int x, int pos) {
return x ^ (1 << pos);
}
};
class Solution {
// 交换两个数
public void swap(int[] nums, int i, int j) {
nums[i] ^= nums[j];
nums[j] ^= nums[i];
nums[i] ^= nums[j];
}
// 查找只出现一次的数
public int findSingle(int[] nums) {
int result = 0;
for (int num : nums) {
result ^= num;
}
return result;
}
// 判断两个数是否相等
public boolean isEqual(int a, int b) {
return (a ^ b) == 0;
}
// 翻转特定位
public int flipBit(int x, int pos) {
return x ^ (1 << pos);
}
}
class Solution:
# 交换两个数
def swap(self, nums: List[int], i: int, j: int) -> None:
nums[i] ^= nums[j]
nums[j] ^= nums[i]
nums[i] ^= nums[j]
# 查找只出现一次的数
def findSingle(self, nums: List[int]) -> int:
result = 0
for num in nums:
result ^= num
return result
# 判断两个数是否相等
def isEqual(self, a: int, b: int) -> bool:
return (a ^ b) == 0
# 翻转特定位
def flipBit(self, x: int, pos: int) -> int:
return x ^ (1 << pos)
时间复杂度分析
| 基本异或 | ||
| 数字交换 | ||
| 查找单数 | ||
| 位翻转 |
应用场景
- 数字加密
- 无临时变量交换
- 查找单一元素
- 校验和计算
- 位状态翻转
注意事项
- 运算优先级
- 自身异或注意
- 溢出处理
- 位数限制
- 性能优化
常见变形
- 数字加密
class Solution {
public:
// 加密
int encrypt(int data, int key) {
return data ^ key;
}
// 解密
int decrypt(int encrypted, int key) {
return encrypted ^ key; // 异或两次恢复原值
}
// 批量加密
vector<int> encryptArray(vector<int>& data, int key) {
vector<int> result = data;
for (int& x : result) {
x ^= key;
}
return result;
}
};
class Solution {
// 加密
public int encrypt(int data, int key) {
return data ^ key;
}
// 解密
public int decrypt(int encrypted, int key) {
return encrypted ^ key; // 异或两次恢复原值
}
// 批量加密
public int[] encryptArray(int[] data, int key) {
int[] result = data.clone();
for (int i = 0; i < result.length; i++) {
result[i] ^= key;
}
return result;
}
}
class Solution:
# 加密
def encrypt(self, data: int, key: int) -> int:
return data ^ key
# 解密
def decrypt(self, encrypted: int, key: int) -> int:
return encrypted ^ key # 异或两次恢复原值
# 批量加密
def encryptArray(self, data: List[int], key: int) -> List[int]:
return [x ^ key for x in data]
- 查找成对数字
class Solution {
public:
// 查找出现奇数次的数字
vector<int> findOddOccurrence(vector<int>& nums) {
int xorSum = 0;
for (int num : nums) {
xorSum ^= num;
}
// 找到最右边的1
int rightmostBit = xorSum & -xorSum;
vector<int> result(2);
for (int num : nums) {
if (num & rightmostBit) {
result[0] ^= num;
} else {
result[1] ^= num;
}
}
return result;
}
};
class Solution {
// 查找出现奇数次的数字
public int[] findOddOccurrence(int[] nums) {
int xorSum = 0;
for (int num : nums) {
xorSum ^= num;
}
// 找到最右边的1
int rightmostBit = xorSum & -xorSum;
int[] result = new int[2];
for (int num : nums) {
if ((num & rightmostBit) != 0) {
result[0] ^= num;
} else {
result[1] ^= num;
}
}
return result;
}
}
class Solution:
# 查找出现奇数次的数字
def findOddOccurrence(self, nums: List[int]) -> List[int]:
xor_sum = 0
for num in nums:
xor_sum ^= num
# 找到最右边的1
rightmost_bit = xor_sum & -xor_sum
result = [0, 0]
for num in nums:
if num & rightmost_bit:
result[0] ^= num
else:
result[1] ^= num
return result
经典例题
牛客代码笔记-牛栋 文章被收录于专栏
汗牛充栋，学海无涯。<br/> 内含算法知识点讲解，以及牛客题库精选例题。<br/> 学习算法，从牛栋开始。
投递蚂蚁集团等公司8个岗位 >
查看3道真题和解析