异或(^) 这个位操作运算符相信大家一定都不陌生，这个运算符可以用来解决很多普通算法解决不了的问题，而且位运算是直接对二进制码做运算，相对普通的加减乘除运算符来说的话更加的高效，我们借着题目一起来看看：
Problem 1
对两个输入参数做加法运算，但是不能使用 “+” 运算符
解法思路：
看到这样的问题，能想到的只有位运算，问题是怎么算？相信大家小学刚学习加法的时候，对于一下子不能得到答案的题，肯定会在草稿纸上列竖式，从右向左算，同一列对下来的数字相加如果超过 10，那么肯定要在下面写两个数字相加后的个位数，然后往前进一位，下一位运算时就要加上这个进位，用这样的方式直到最后算出结果。这题的思路也是一样的，只不过有两点不一样，第一，10 进制变成了 2 进制，第二，我们不再是在草稿纸上列竖式，而是要写成计算机看得懂的代码，这就得借助我们的位运算了，因为 2 进制表示的数中只会出现 0 和 1，你可以把这两个数看成是 true 和 false，这样更好理解，我们可以先通过异或塞选出不用进位的情况，然后再用与运算和左移运算计算出进位的情况，迭代更新出最后的结果。
参考代码：
public int plus(int a, int b) {
int aTemp = 0, bTemp = 0;
while (b != 0) {
aTemp = a ^ b;
bTemp = (a & b) << 1;
a = aTemp;
b = bTemp;
}
return a;
}
Problem 2
How to do swap without creating temporary variable
解法思路：
异或的常见应用，很简单，但是注意思考角度从位出发，而不是数，这点很重要。
参考代码：
public void swap(int a, int b) {
a ^= b; // a 中存放两数互异的点位
b ^= a; // 取反 b 中不同于 a 的点位，也就是实现了 b = a
a ^= b; // 取反 a 中不同于 b 的点位，也就是实现了 a = b
}
Problem 3
If convert A to B, how many bits needed to be changed?
解法思路：
异或的简单应用，两个数做异或的结果就是两个数差异所在，然后只需计算这个结果中有多少个 1 即可。
参考代码：
public int convertA2B(int A, int B) {
int n = A ^ B;
int count = 0;
while (n != 0) {
n = n & (n - 1); // n - 1 是将 n 的最低位为零
count++;
}
return count;
}
Problem 4
Given a non-empty array of integers, every element appears twice except for one. Find that single one.
解法思路：
异或的三个点顺下来，就可以很清楚地解这道题：
异或运算和乘法一样，位置和运算顺序不影响最后结果：a^b^c = b^c^a
两个相同的数做异或运算结果为零：a^a = 0
任何数和零做异或结果还是这个数本身：a^0 = a
参考代码：
public int findOnce(int[] arr) {
int result = 0;
for (int i = 0; i < arr.length; ++i) {
result ^= arr[i];
}
return result;
}
Problem 5
Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
解法思路：
这题的难点在于 3 次，如果把数组里面的数字就当作数字本身来看的话，很难找到突破口；如果想到了位运算，那就要有一个概念就是位运算是基于位的，而不是基于数的，在这个问题中，所有的 bit 的出现次数只会有两种情况，3*n，3*n + 1,这里的 n 是任意整数，假设你遍历数组，其实会有一个中间态就是 3*n + 2 存在，对于除这个数以外的其他数，过程大概是 3*n + 1 -> 3*n + 2 -> 3*n，我们只要记录的就是 3*n + 1 和 3*n + 2的情况，因为 3*n 其实就是一个初始状态（n=0）,记不记录和我们最后要返回的答案无关，而记录 3*n + 2 是为了恢复一些 bit 从 3*n + 2 到 3*n
参考代码：
public int singleNumber(int[] nums) {
int ones = 0, twos = 0;
for (int i = 0; i < nums.length; ++i) {
// 找出当前的 3n + 1
ones = (nums[i] ^ ones) & (~twos);
// 找出当前的 3n + 2
twos = (nums[i] ^ twos) & (~ones);
}
return ones;
}
Problem 6
LeetCode 260 Single Number III
Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
解法思路：
这题的主要难点是如何把两个数给拆出来，如果直接运用异或算法，我们最后得到的结果是两个数做异或的结果，关键点是如何基于这个异或的结果来找到这两个数，有一点很重要的就是，异或的结果为 1 的点位只会出现在其中一个数中，我们可以用其中一个为 1 的点位作为判断依据，这个点位存在的所有数在一起做异或，这个点位不存在的所有数一起做异或，这样就把这个问题拆解成了两个 problem 3。
参考代码：
public int[] singleNumber(int[] nums) {
if (nums == null || nums.length == 0) {
return new int[2];
}
int different = 0;
for (int i : nums) {
different ^= i;
}
different &= -different;
int[] ans = {0, 0};
for (int i : nums) {
if ((different & i) == 0) {
ans[0] ^= i;
} else {
ans[1] ^= i;
}
}
return ans;
}
总结：
位运算相对其他的运算来说更加的高效，异或在位运算中的应用非常广，但是这里的难点是我们平时可能会忽视位运算，导致我们遇到一般的问题不会往位运算的方向去想，另外就是如果对二进制的运算不熟，我们也很难理解一些位运算的综合操作，这里提到了异或可以交换两个数，做加法操作，还可以用来解决一些问题。
也欢迎你来分享你对异或以及位运算的认识
