位运算规律与相关题解
正文
位运算是计算机中效率最高的一种运算方式，若能将原来的运算通过位运算实现，将会大大提高我们的算法效率。就运算速度来讲，大部分情况下：
位运算 > 加减 > 乘除 > 幂运算
位运算规律
交换律：
a & b = b & a
a | b = b | a
a ^ b = b ^ a
结合律（仅适用于单个位运算符）：
(a | b) | c = a | (b | c)
(a & b) & c = a & (b & c)
(a ^ b) ^ c = a ^ (b ^ c)
分配律：
(a & b) | c = (a | c) & (b | c)
(a | b) & c = (a & c) | (b & c)
(a ^ b) & c = (a & c) ^ (b & c)
其中，第三条规律是唯一一条，有「异或」运算情况下满足配率。
位运算抵消：
a & (~a) = 0
a ^ a = 0
判断奇偶：
a & 1 == 0 ? 奇 : 偶
保留二进制中末位的1：
a & -a
a & (~a + 1)
注：(~a + 1)是a的补码表现形式，即-a
去除二进制中的末位1：
a & (a – 1)
只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
Eg.
输入：[4, 1, 2, 1, 2]
输出：4
就普遍理性而论，这道题有许多的解法，但若想要达到O(1)的空间复杂度和线性的时间复杂度，使用位运算是为数不多的方法。利用位运算中异或运算的以下三个性质：
a ^ 0 = a
a ^ a = a
a ^ b = b ^ a
可以将输入数组中所有出现偶数次的元素相消为0，留下唯一奇数次的目标数。
int singleNumber(int[] nums) {
int res = 0;
for (int num : nums) {
res ^= num;
}
return res;
}
只出现一次的数字 II
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
Eg.
输入：nums = [1, 2, 1, 3, 2, 5]
输出：[3, 5] 或 [5, 3]
假设我们寻找的目标数是a和b，利用上一题的经验，我们很快可以想出使用异或运算来消除输入数组中所有出现两次的元素。但由于目标数有两个，所以最后我们获取的结果值是a ^ b，我们用一个变量xorsum将其存储。
根据题意，我们知道a不等于b，因此a ^ b的值不为0，既xorsum不会为0，那我们可以通过xorsum来确认a与b二进制表示中不同的某一位。利用与运算xorsum & -xorsum，保留xorsum二进制的末位1，假设其为第j位。
那么回到a和b，因为a ^ b的产物xorsum的第j位为1，所以a和b的二进制表示中，第j位必然是不同的。那么我们可以根据这一条件，将输入数组中的数区分为两类，其中一类，所有数的二进制表达中第j位是1；另一类则是0。而a和b分别在这两类数之中，并且输入数组中出现两次的数，出现的两次都会被包含在同一类中。所以我们将这两类数全部异或起来，便能得到我们需要的两个结果。
int[] singleNumber(int[] nums) {
int res1 = 0, res2 = 0, xorsum = 0;
for (int num : nums) {
xorsum ^= num;
}
// 保留ero二进制中的最后一位
xorsum &= -xorsum;
for (int num : nums) {
if ((xorsum & num) == 0) {
// 一类
res1 ^= num;
} else { // (ero & num) != 0
// 另外一类
res2 ^= num;
}
}
return new int[]{res1, res2};
}
只出现一次的数字 III
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
Eg.
输入：nums = [0, 1, 0, 1, 0, 1, 99]
输出：99
注：往下的内容，需要读者对数字电路设计有一定的基础。
利用上面两题的经验，我们第一想法必然是使用异或运算进行相消……显然是不可行的，因为异或运算只能区别偶数和奇数次的元素。那我们如何区别都是奇数次的元素呢？
其实使用异或运算来消除出现偶数次的数字，和二进制的进位有些相似。一个数字出现两次，就会因为异或相消，既1 ^ 1 = 0；而二进制则是1 + 1 = (1)0，只是二进制中我们只对固定一位进制进行处理。
那么对于这一题，我们可以考虑构建出一种新的二元运算方式，使得出现3次的数相消为0，而保留出现1次的数字。类似于三进制，1 + 1 + 1 = (1)0，但计算机底层仍是使用二进制表示的，所以我们需要多一个数加以辅助，为了方便后续表达，这两个数我设为x和y，x和y表达的3进制数我设为R，并且具有以下规律：
R = 0时，x = 0，y = 0
R = 1时，x = 0，y = 1
R = 2时，x = 1，y = 0
假设我们需要寻找的数为res，那么res首次出现时，R = 1；第二次出现时，R = 2；第三次出现时，R = 0。
综上，我们可以获得以下真值表：
x | y | res | 新的x | 新的y | R |
0 | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 0 | 0 | 1 | 1 |
1 | 0 | 0 | 1 | 0 | 2 |
0 | 0 | 1 | 0 | 1 | 1 |
0 | 1 | 1 | 1 | 0 | 2 |
1 | 0 | 1 | 0 | 0 | 0 |
进而写出x和y分别对应的逻辑表达式（编程语言表达，没有使用代数法进行简化）：
x = (x & ~y & ~res) | (~x & y & res)
y = (~x & y & ~res) | (~x & ~y & res)
由此，当我们对数组中所有的元素作完处理后，x必然为0，y则是出现1次的数，所以我们返回y即可。题外话，若题目中的目标数是出现了2次，既R = 2，此时x = 1，y = 0，此时我们返回的应该是x。
int singleNumber(int[] nums) {
int x = 0, y = 0;
for (int num : nums) {
// 先运算，结果存储至临时变量中，再赋值
int tempX = (x & ~y & ~num) | (~x & y & num);
int tempY = (~x & y & ~num) | (~x & ~y & num);
x = tempX;
y = tempY;
}
return y;
}