1. 基本原理
x ^ 0s = x x & 0s = 0 x | 0s = x
x ^ 1s = ~x x & 1s = x x | 1s = 1s
x ^ x = 0 x & x = x x | x = x
- 利用
x ^ 1s = ~x的特点，可以将位级表示翻转；利用x ^ x = 0的特点，可以将三个数中重复的两个数去除，只留下另一个数。 - 利用
x & 0s = 0和x & 1s = x的特点，可以实现掩码操作。一个数 num 与 mask：00111100 进行位与操作，只保留 num 中与 mask 的 1 部分相对应的位 - 利用
x | 0s = x和x | 1s = 1s的特点，可以实现设值操作。一个数 num 与 mask：00111100 进行位或操作，将 num 中与 mask 的 1 部分相对应的位都设置为 1
位运算技巧：
-
n&(n-1)去除 n 的位级表示中最低的那一位。例如对于二进制表示 10110100，减去 1 得到 10110011，这两个数相与得到 10110000。 -
n&(-n)得到 n 的位级表示中最低的那一位。-n 得到 n 的反码加 1，对于二进制表示 10110100，-n 得到 01001100，相与得到 00000100。 -
n-n&(~n+1)去除 n 的位级表示中最高的那一位
2. 计算
540. 有序数组中找出单独存在的数，其余的数都是成对出现 Single Element in a Sorted Array
法1. 时间复杂度O(n) 空间复杂度O(2)
使用stack，利用有序和成对出现pop+push，最后stack的最后一个值是单数
法2. 时间复杂度O(n) 空间复杂度O(1)
利用数学^异或公式-> x ^ 0 = x, x ^ x = 0，遍历最后剩下的是单数
法3. 时间复杂度O(logn) 空间复杂度O(1)
折半法，每次将后一半的值与前一半的值做^异或，如果计算长度是奇数对nums[0]^=nums[mid]，折半缩小范围
