位运算是我最近才开始重视的东西，因为在LeetCode上面刷题的时候发现很多题目使用位运算会快很多。位运算的使用包含着许多技巧（详细可以参考http://blog.csdn.net/zmazon/article/details/8262185），但我仅仅在大一学C语言入门的时候接触过，很多东西都不了解，因此我在这篇文章里面稍微总结一下我在LeetCode遇到的关于位运算的题目，当然仅仅只是一部分，因此这篇文章可能会在我每次遇到位运算的题目时更新一下。
首先要回忆一下有哪些位运算的操作：
| 按位与 | a&b |
| 按位或 | a|b |
| 按位异或 | a^b |
| 按位取反 | ~a |
| 左移 | a<<b |
| 右移 |
a>>b |
然后就是LeetCode上面的题目了：
（1）136. Single Number（https://leetcode.com/problems/single-number/description/）
给定一个数组，数组中的每一个值在数组里面都出现了2次，只有一个值只出现了1次，要求我们把它找出来。
一般的思路肯定是开辟一块空间来操作（类似于桶）或者排序然后查找，但题目里面有这样一个提示“Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?”，“linear runtime complexity”，即要求在O(n)的时间复杂度里面完成，先排序的方法肯定不行了；“without using extra memory”，另一种想法也抹杀掉。
在这种情况下，我们可以使用位运算中的异或来帮助我们解题。（我发现有特别提示的题目一般都会有“投机取巧”的解题方法，比如这一题的位运算）我们可以发现，一个数与它自己本身进行异或操作，结果肯定为0；0和一个数做异或操作，结果肯定为这个数，利用这一点，我们就可以很好地在O(n)的时间复杂度里面解决问题：
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = 0;
for (int i = 0; i < nums.size(); i++) {
res ^= nums[i];
}
return res;
}
};
（2）268. Missing Number（https://leetcode.com/problems/missing-number/description/）
这一题给出一个值连续的数组，只不过在中间抽掉了一个值，让我们找出来。我们可以先根据给出的数组大小求出本来的结果（即没有抽掉数的总和），然后求出现在的总和，两者相减，就可以得出结果。这是一种方法：
class Solution {
public:
int missingNumber(vector<int>& nums) {
int sum = ;
for (int i = ; i < nums.size(); i++) {
sum += nums[i];
}
int actual_sum = nums.size() * (nums.size() + ) /;
return actual_sum - sum;
}
};
当然还有用位运算解决的方法，也是异或，原理也是上面一题的原理。只不过为了要用到“一个数与它自己本身进行异或操作”这一点，我们需要在原基础上增加一个变量，使一个数能出现两次：
class Solution {
public:
int missingNumber(vector<int>& nums) {
int res = ;
int temp = ;
for (int i = ; i < nums.size(); i++) {
res ^= nums[i] ^ temp;
temp++;
}
return res;
}
};
从上面两题中，我们是不是总结出一点呢？当题目给出一堆数，其中的一个数的数量和其他数不同，要求把它找出来，我们可以考虑使用位运算中的异或操作解决。
（3）191. Number of 1 Bits（https://leetcode.com/problems/number-of-1-bits/description/）
这一题要求一个数的二进制数中有几个1。我们只需要将这个数不断地右移，然后和与1按位相与，直到这个数为0即可。假如一个数的最右一位为0，与1相与为0；为1，与1相与为1。代码如下：
class Solution {
public:
int hammingWeight(uint32_t n) {
int res = ;
while (n) {
res += (n & );
n = n >> ;
}
return res;
}
};
（4）求一个数是否2的幂
这道题在我的另一篇博客里面有讨论，不展开了。
http://www.cnblogs.com/fengziwei/p/7570885.html
（5）371. Sum of Two Integers（https://leetcode.com/problems/sum-of-two-integers/description/）
这道题就是用位运算实现正整数加法，投机取巧也能过，但这就没意思了。
加法的实现，无非就是当前位相加，然后考虑进位即可。不考虑进位，0+0为0，1+0为1，1+1为0，这是异或的操作。然后考虑进位，只有1+1的时候才需要进位，因此可以先将当前位相与，再将结果左移1位。因为不能用加法，所以要利用循环，当没有进位的时候结束。具体代码如下：
class Solution {
public:
int getSum(int a, int b) {
int res = a ^ b;
int temp = (a & b) << ;
while (temp) {
cout << res << endl;
cout << temp << endl;
int copy = res;
res = res ^ temp;
temp = (copy & temp) << ;
}
return res;
}
};
（6）461. Hamming Distance（https://leetcode.com/problems/hamming-distance/description/）
class Solution {
public:
int hammingDistance(int x, int y) {
int temp = x ^ y;
int res = ;
while (temp) {
res += temp & ;
temp >>= ;
}
return res;
}
};
未完待续。。。。。。