前言
今天看雪花算法，其中有这样一个运算-1 ^ -1 << 5
当然，这个运算是我替换变量之后得到的，不是原文
然后，我就懵了，我虽然知道移位和异或，但我不知道运算顺序，更不用说运算目的和结果了
既然如此，那就好好补课吧
运算优先级
参考这里，得到运算优先级，由高到低如下：
| 加减 | 移位 | 比较大小 | 位与 | 异或 | 位或 |
|---|---|---|---|---|---|
| +,— | «,» | >,<,==,!= | & | ^ | | |
所以第一个问题结论有了：先移位，后异或
负数和二进制的转换
要做移位，先要转二进制，那么如何将一个负数转为二进制呢？
方法参考这里，步骤如下：
- 将其绝对值转化为二进制
- 按位取反，得到反码
- 反码加一，得到补码，补码就是负数
- 若要补齐8位或者16位，则在前面补 1
二进制负数转十进制，过程是相反的：
- 二进制减一
- 按位取反
- 计算
- 前面追加负号
异或运算
规则见这里，总结如下：
- 补码运算（正数补码即本身，负数补码为按位取反后加一）
- 按位异或，相同为0，不同为1
- 一个数字异或其本身为0，即
A ^ A = 0 - 一个数字异或0为其本身，即
A ^ 0 = A - A ^ B ^ C = (A ^ B) ^ C = A ^ (B ^ C)
实践
有了上面的准备，-1 ^ -1 << 5 运算就可以做了，其步骤如下：
二进制：00000001
得反码：11111110
得补码：11111111
移位后：11100000
异或后：00011111
计算：2^4+2^3+2^2+2^1+2^0=31，当然，这个^就不是异或的意思了，而是乘方的意思
校验
刚才的运算好像有点简单，再找一个校验下
看到了这个，题主已经说了-100 ^ -1 = 99，而不是100
先计算100的二进制：
2/100
2/50 0
2/25 0
2/12 1
2/6 0
2/3 0
2/1 1
0 1
则100的二进制为：1100100，校验一下：2^6+2^5+2^2=100
重复之前的步骤：
01100100 二进制
10011011 得反码
10011100 得补码
11111111 二进制负一
01100011 异或后
校验一下：2^6+2^5+2^1+2^0=99
结论
-1 ^ -1 << 5运算，其实起到的作用就是2 ^ 5 - 1的效果
其他应用场景
主要用到了异或的这么几点：
- 一个数字异或其本身为0，即
A ^ A = 0 - 一个数字异或0为其本身，即
A ^ 0 = A - A ^ B ^ C = (A ^ B) ^ C = A ^ (B ^ C)
问题一：找出2n+1个数中不成对的那个
原文见这里
问题定义：有2n+1个数，只有一个单着，别的都是成对的，找出这个单着的数。比如：2 1 3 2 1。答案是 3
解题思路：将所有数异或，成对的为0，剩下那个就是答案
问题二：找出n个数中唯一重复的那个
原文见这里和这里
问题定义：1-1000放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现一次。每个数组元素只能访问一次，设计一个算法，将它找出来
解题思路：
- 计算1~1000的异或值
1^2^3……998^999^1000=T - 计算数组中所有值的异或
N0^N1^N2……N998^N999^N1000=T^n，N是数组，0~1000是下标 - 将 1 和 2 的值再做异或
T^T^n=n，n就是那个唯一的值