最近刷LettCode，遇到几个没思路的算法题，都是关于位运算的
# 136 Single Number
Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Example 1:
Input: [2,2,1]
Output: 1
Example 2:
Input: [4,1,2,1,2]
Output: 4
找出成对数数组中的那个单身狗（成天吃狗粮干什么）
- O(n^2)思路
先将数组进行排序，然后每次比较相邻的两个数且前进2个，出现不相等则输出第一个数；
- O(nlogn)思路
改进排序算法，采用快排
- 最终解决思路O(n)
迭代一次数组通过位运算，最后得出结果即数组中的单身数。
原理：
0 xor any = any；1 xor any = ~any；any xor any = any
异或运算的feature使得再出现两个相同的数时，异或结果会变成0，而其中不成双的数最后相当于与0异或得以留存下来
代码：
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans=;
for(int e : nums){
ans ^= e;
}
return ans;
}
};
# 371 Sum of Two Integers
Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.
Example 1:
Input: a = 1, b = 2
Output: 3
Example 2:
Input: a = -2, b = 3
Output: 1
不使用+，-运算符进行两数的相加，这题第一时间还真没思路
原理：
通过位运算模拟两数相加的过程
- 两数在二进制下相加，不考虑进位的情况下，如果某位上分别是1，0则该位结果为1；若都是1则结果是0；都是0也是0；这情况和异或一致，这样我们将两数异或就得到了未进位下的两数和。
- 而发生进位则是两数对应位上都是1的情况，这时候我们通过按位与操作，得到需要进位的位置，然后进行左移就是每个位需要加上的进位。
- 将未进位的数之和 同 发生的进位相加（注意这里又相当于两数相加），就得到了结果。
- 同时上一步的又会产生新的进位，我们需循环到进位为零的情况
注意：C++中的负数的左移操作最后会变为最小的负整数而不是0，所以需要对进位数进行截取 => carry = caryy & 0x7FFFFFFF (整型长32位)
代码：
class Solution {
public:
int getSum(int a, int b) {
int carry;
while(b){
carry = a & b & 0x7FFFFFFF;
a = a ^ b;
b = carry << ;
}
return a;
}
};