位运算基础性质
- &按位与：全1为1，其他为0
- |按位或：有1就1，全0才0
- ^按位异或：不同为1，相同为0
&一般用于寻找二进制下1的位置
|一般用于改变一个二进制位置的值
（参考布隆过滤器的使用）
异或性质：6 ^ 0=6，6 ^ 6=0，2 ^ 2 ^ 3=2 ^ 3 ^ 2=3（交换律）
补充：计算机中的负数为反码的补码
举个int型例子，8位：
-10的二进制：1000 1010；反码：1111 0101；补码：1111 0110
因此10 & (-10)的结果为0000 0010 ，即下面第二题确定一个二进制第一次出现1的位置的原理
第一题
题目要求元素都重复两次，只有一个元素不重复，根据异或定义，直接将数组中所有元素全部异或的值即为出现一次的元素
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ret = 0;
for (auto e: nums) ret ^= e;
return ret;
}
};
第二题
题目链接
与前一题不同的是，有两个单独出现的元素，此时依然用第一题全部异或一遍的话最后结果为那两个不重复元素的异或值
此时，我们可以考虑一种策略进行分组，这个策略恰巧可以将连个单独出现的元素分成两部分；同时，其他两两出现的重复元素根据策略必定出现相同的元素在一边
根据以前通过&1操作来区分数字的奇偶（数转二进制后最后（最右）一位为0表示偶数，反之为奇数），我们也可以用此思想来分两个单独出现的元素。
由于两个单独出现的元素异或结果中，通过二进制角度来看，出现1的地方一定是两个数二进制时不同的地方，因此通过寻找第一个出现不同二进制的位置来作为分组策略
最后将所有值与这个分组策略的数进行&，两部分的值即为两个单独出现的数
另外注意的是，寻找分组策略数的过程，可以直接通过n&(-n)的结果来确定，答案与下面的一次移位寻找的结果相同。
class Solution {
public:
vector<int> singleNumbers(vector<int>& nums) {
int n=0;
int m=1;
int x=0,y=0;
for(int num:nums){
n^=num;
}
while((m&n)==0){
m<<=1;
}
for(int num:nums){
if(num&m) x^=num;
else y^=num;
}
return vector<int> {
x,y};
}
};
第三题
此题与第一题不同的是，重复元素每次都出现三次
因此第一题，第二题的方法均不行
由于重复元素都出现三次，因此可以将每次出现的元素的二进制位相加，最后将位置上的值和3求余，只要有余数的就是那个单独出现的元素多加了一次导致的
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res=0;
for(int i=0;i<32;i++){
int count=0;
for(int j=0;j<nums.size();j++){
if((nums[j]>>i&1)==1){
count++;
}
}
if(count%3!=0){
res=res|1<<i;
}
}
return res;
}
};