异或运算
-
异或运算就是无进位相加
-
异或运算满足交换律、结合律
-
0^n = n，n^n = 0
-
整体异或和为 x，整体中某个部分的异或和为 y，那么剩下的部分的异或和为 x^y。即若 a^b = c，则 a = c^b，b = c^a
交换两个数
#include <iostream>
#include <vector>
using namespace std;
// i == j 时会出错
void mySwap(vector<int> &arr, int i, int j) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
int main() {
// 两个变量必须有独立的内存空间
int a = 211;
int b = -985;
a = a ^ b;
b = a ^ b;
a = a ^ b;
cout << a << " " << b << endl;
vector<int> arr{1, 2, 3};
mySwap(arr, 0, 1);
cout << arr[0] << arr[1] << arr[2] << endl;
// 同一个内存空间，会变成 0
mySwap(arr, 2, 2);
cout << arr[0] << arr[1] << arr[2] << endl;
}
返回最大值
package org.example;
public class Main {
// 必须保证 n 一定是 0 或者 1
// 0 变 1，1 变 0
public static int flip(int n) {
return n ^ 1;
}
// 非负数返回 1
// 负数返回 0
public static int sign(int n) {
// 无符号右移
return flip(n >>> 31);
}
// 有溢出风险的实现
public static int getMax1(int a, int b) {
int c = a - b;
// c非负，returnA -> 1
// c非负，returnB -> 0
// c负数，returnA -> 0
// c负数，returnB -> 1
int returnA = sign(c);
int returnB = flip(returnA);
return a * returnA + b * returnB;
}
// 没有任何问题的实现
public static int getMax2(int a, int b) {
// c 可能是溢出的
int c = a - b;
// a 的符号
int sa = sign(a);
// b 的符号
int sb = sign(b);
// c 的符号
int sc = sign(c);
// 判断 A 和 B，符号是不是不一样，如果不一样 diffAB = 1，如果一样 diffAB = 0
int diffAB = sa ^ sb;
// 判断 A 和 B，符号是不是一样，如果一样 sameAB = 1，如果不一样 sameAB = 0
int sameAB = flip(diffAB);
int returnA = diffAB * sa + sameAB * sc;
int returnB = flip(returnA);
return a * returnA + b * returnB;
}
public static void main(String[] args) {
int a = Integer.MIN_VALUE;
int b = Integer.MAX_VALUE;
// getMax1 方法会错误，因为溢出
System.out.println(getMax1(a, b));
// getMax2 方法永远正确
System.out.println(getMax2(a, b));
}
}
136. 只出现一次的数字
#include <vector>
using namespace std;
class Solution {
public:
int singleNumber(vector<int> &nums) {
int XOR = 0;
for (const auto &item: nums)
XOR ^= item;
// 最终出现在异或运算中两次的数字会抵消变成 0，最后单独出现的那个就是丢失的，因为没人和他抵消
return XOR;
}
};
268. 丢失的数字
#include <vector>
using namespace std;
class Solution {
public:
int missingNumber(vector<int> &nums) {
int n = nums.size();
int XOR = 0;
for (int i = 0; i < n; ++i) {
// 这句保证了[0,n]中除了丢失的那个数全都参与异或运算
XOR ^= nums[i];
// 这句和结尾的 return 保证了[0,n]全都参与异或运算
XOR ^= i;
}
return XOR ^ n;
// 最终出现在异或运算中两次的数字会抵消变成 0，最后单独出现的那个就是丢失的，因为没人和他抵消
}
};
260. 只出现一次的数字 III
- Brian Kernighan 算法：
n & (~n + 1)提取出整数n最后一位为1的数，等价于n & (-n)
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> singleNumber(vector<int> &nums) {
int xorSum = 0;
for (const auto &num: nums)
xorSum ^= num;
// 此时 xorSum == a ^ b，xorSum 的二进制中，在 k 位置为 1，说明在 a 和 b 中的 k 位置是相反的
// 防止溢出
int rightOne = (xorSum == INT_MIN) ? xorSum : (xorSum & (~xorSum + 1));
// int rightOne = (xorSum == INT_MIN) ? xorSum : (xorSum & (-xorSum));
int xorSum2 = 0;
for (const auto &num: nums) {
// 只异或上 k 位置为 0 的数，最终结果就是 a 和 b 中的一个
if ((num & rightOne) == 0)
xorSum2 ^= num;
}
return vector<int>{xorSum2, xorSum ^ xorSum2};
}
};
137. 只出现一次的数字 II
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
// 已知数组中只有 1 种数出现次数少于 m 次，其他数都出现了 m 次
// 返回出现次数小于 m 次的那种数
int find(vector<int> &nums, int m) {
vector<int> counts(32, 0);
// 统计每一位上 1 出现的次数
for (const auto &num: nums)
for (int i = 0; i < 32; ++i)
counts[i] += (num >> i) & 1;
int res = 0;
for (int i = 0; i < 32; ++i)
// 查看余数不是 0 的位置
if (counts[i] % m != 0)
res |= (1 << i);
return res;
}
int singleNumber(vector<int> &nums) {
return find(nums, 3);
}
};