前置知识：二进制和位运算
特别提醒：Python 的同学实现位运算的题目需要特别注意，需要自己去手动处理溢出和符号扩展等问题，比如：
(n << shift_amount) & 0xFFFFFFFF（Python 溢出会自动升位：）
先来一个好玩的问题
袋子里一共 a 个白球，b 个黑球，每次从袋子里拿 2 个球，每个球每次被拿出机会均等
如果拿出的是 2 个白球、或者 2 个黑球，那么就往袋子里重新放入 1 个白球
如果拿出的是 1 个白球和 1 个黑球，那么就往袋子里重新放入 1 个黑球
那么最终袋子里一定会只剩 1 个球，请问最终的球是黑的概率是多少？用 a 和 b 来表达这个概率。
被镇住了吧？其实这题是一个陷阱。
答案：
黑球的数量如果是偶数，最终的球是黑的概率是 0%
黑球的数量如果是奇数，最终的球是黑的概率是 100%
完全和白球的数量无关。为啥？异或运算的性质了解之后，就了解了。
异或运算性质
- 异或运算就是无进位相加
- 异或运算满足交换律、结合律，也就是同一批数字，不管异或顺序是什么，最终的结果都是一个
0 ^ n = n，n ^ n = 0- 整体异或结果如果是
x，整体中某个部分的异或结果如果是y，那么剩下部分的异或结果是x ^ y
这些结论最重要的就是 1 结论，所有其他结论都可以由这个结论推论得到
其中 4 结论相关的题目最多，利用区间上异或和的性质
回头看 前面的题，把白球看成 0，黑球看成 1，原问题等价于将 a 个 0 和 b 个 1 整体异或起来结果是啥
Nim 博弈也是和异或运算相关的算法，将在后续【必备】课程里讲到
题目
1.交换两个数
func swap(a, b *int) {
*a = *a ^ *b
*b = *a ^ *b
*a = *a ^ *b
}解释：
a = 甲, b = 乙
a = a ^ b // 甲 ^ 乙
b = a ^ b // (甲 ^ 乙) ^ 乙 = 甲
a = a ^ b // (甲 ^ 乙) ^ 甲 = 乙坑：a 和 b 不能指向同一个地址
func main() {
arr := [2]int{23, -9999}
swap(&arr[0], &arr[1])
fmt.Println(arr) // [-9999 23]，正确
swap(&arr[0], &arr[0])
fmt.Println(arr[0]) // 0，坑！
}
func swap(a, b *int) {
*a = *a ^ *b
*b = *a ^ *b
*a = *a ^ *b
}相当于：
a = 甲, b = 甲（注意：不要将同一个地址和相同数混淆，相同数运算是正确的）
a = a ^ b // 甲 ^ 甲 = 0
b = a ^ b // 0 ^ 0 = 0
a = a ^ b // 0 ^ 0 = 0所以知道这种写法即可，并不推荐
2.获取最大值
不用任何判断语句和比较操作，返回两个数的最大值
测试链接：获取最大值
// 不用任何判断语句和比较操作，返回两个数的最大值
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 可能溢出
// 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) {
int c = a - b; // 这里 c 可能溢出
int sa = sign(a); // a 的符号
int sb = sign(b); // b 的符号
int sc = sign(c); // c 的符号
// 判断 A 和 B 符号是不是不一样，如果不一样 diffAB=1，如果一样 diffAB=0
int diffAB = sa ^ sb;
// 判断 A 和 B 符号是不是一样，如果一样 sameAB=1，如果不一样 sameAB=0
int sameAB = flip(diffAB);
// diffAB * sa: a 和 b 符号不一样且 a 非负
// sameAB * sc: a 和 b 符号一样且 c 非负
// 这两种情况下 c 不可能溢出
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));
}
}Go 中没有无符号右移操作（如何解决？），实现起来比较复杂，这里写 Java 代码
3.找到缺失的数字
测试链接：268.丢失的数字
func missingNumber(nums []int) int {
res := 0
for i := 0; i < len(nums); i++ {
res ^= nums[i]
res ^= i
}
res ^= len(nums)
return res
}4.只出现一次的数字
数组中 1 种数出现了奇数次，其他的数都出现了偶数次，返回出现了奇数次的数
测试链接：136.只出现一次的数字
func singleNumber(nums []int) int {
xor := 0
for _, num := range nums {
xor ^= num
}
return xor
}5.只出现一次的数字 III
数组中有 2 种数出现了奇数次，其他的数都出现了偶数次，返回这 2 种出现了奇数次的数
测试链接：260.只出现一次的数字 III
func singleNumber(nums []int) []int {
// a、b 为出现奇数次的两个数
eor := 0
for _, num := range nums {
eor ^= num
}
// 现在 eor = a ^ b
// 因为 a != b，所以 eor 二进制中必定有是 1 的位
rightOne := eor & (-eor) // Brian Kernighan 算法：提取出二进制状态中最右侧的 1
eor2 := 0
for _, num := range nums {
if num&rightOne == 0 { // rightOne 位不是 1 的数
eor2 ^= num
}
}
// 现在 eor2 = a
// 则 b = eor ^ eor2 = a ^ b ^ a
return []int{eor2, eor ^ eor2}
}Brian Kernighan 算法
提取出二进制状态中最右侧的 1
原数 n 01101000
要求变成 00001000 // 只保留最右侧的 1
n 01101000
^n 10010111
^n+1 10011000
^n+1 10011000
& n 01101000
-----------------
00001000
即：n & (-n)6.只出现一次的数字 II
数组中只有 1 种数出现次数少于 m 次，其他数都出现了 m 次，返回出现次数小于 m 次的那种数
const (
INT_BIT_COUNT = int(unsafe.Sizeof(int(0)) * 8) // int 占的位数
)
func singleNumber(nums []int) int {
return find(nums, 3)
}
// 更通用的方法
// 已知数组中只有1种数出现次数少于 m 次，其他数都出现了 m 次
// 返回出现次数小于 m 次的那种数
func find(nums []int, m int) int {
// cnts[i] : 二进制中 i 位上有多少个 1
cnts := [INT_BIT_COUNT]int{}
for _, num := range nums {
for i := 0; i < INT_BIT_COUNT; i++ {
cnts[i] += (num >> i) & 1
}
}
ans := 0
for i := 0; i < INT_BIT_COUNT; i++ {
if cnts[i]%m != 0 {
ans |= 1 << i
}
}
return ans
}