性质：

• ａ＾ｂ＝ｂ＾ａ
• ａ＾ｂ＾ｃ＝ａ＾（ｂ＾ｃ）
• ａ＾０＝ａ
• ａ＾ａ＝０；

在刷题上主要应用的是【异或】的自反省，即Ａ＾Ｂ＾Ｂ＝Ａ，依此性质出现的题目层出不穷 应用1：交换ａ与ｂ

t=a^b;
a=a^t;
b=b^t;

应用2：在一列数组中，其中数字均成双出现，仅有一个数字仅出现一次，求该【单身狗】。 直接将整个数组异或求解，解便是该 【单身狗】

剑指 Offer 56 - I. 数组中数字出现的次数

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

异或及按位分组——分治

思路

显然，对于nums中仅有1个孤独数字，可直接通过全局异或得到该值。但如何求解2个不同孤独数字呢?应用上述思想，将数组按如下条件分组，便可求得：

1. 相同数字分为同一组
2. 孤独数字分为不同组

故该问题转化为如上两个子问题。

设对nums异或所得为x，两个【孤独数字】分别为a,b;将x按位展开,显然有^;取任意==1，不同。故依据该位进行分组，该位为0的为一组，该位为1的一组，必然满足如上两个条件：

1. 相同数字该位必然相同，故必然为同一组，成立
2. 由于==1，表示在该位a,b并不相同，所以必然不为同一组，成立

   算法

• 求x
• 找到x从左到右第一个为1的位

• 按位分组，并异或求值

  实现

  ```cpp vector singleNumbers(vector& nums) { int x = 0; for (int v : nums)

    x ^= v;

  /**

  • 快速求取x的第一位1

  • flag=x&(~x+1) */ int flag=x&(~x+1);

    int a=0,b=0; for(auto val:nums){ if(flag&val)

      a^=val;

    else

      b^=val;

    } return {a,b}; return {a, b}; }

<a name="7k4jf"></a>
## 复杂度分析
- 时间复杂度:![](https://cdn.nlark.com/yuque/__latex/33697ce7dfa48ba80980d298c8089378.svg#card=math&code=O%28N%29&height=20&width=41)
- 空间复杂度:![](https://cdn.nlark.com/yuque/__latex/5e079a28737d5dd019a3b8f6133ee55e.svg#card=math&code=O%281%29&height=20&width=34)
<a name="2EkSB"></a>
# ☆☆☆[137. 只出现一次的数字 II](https://leetcode-cn.com/problems/single-number-ii/)
> 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了**三次**。找出那个只出现了**一次**的元素。
> 
> 说明：
> 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
> 
<a name="i7EcZ"></a>
### 思路
XOR<br />该运算符用于检测出现奇数次的位：1、3、5 等。<br />以此类推，只有某个位置的数字出现奇数次时，该位的掩码才不为 0。<br />![](https://cdn.nlark.com/yuque/0/2021/png/2728415/1614845763726-45f0ba7d-a232-4f4a-b4e8-214d8747f5d9.png#align=left&display=inline&height=324&margin=%5Bobject%20Object%5D&originHeight=922&originWidth=1512&size=0&status=done&style=none&width=532)<br />**因此，可以检测出出现一次的位和出现三次的位，但是要注意区分这两种情况。**
<a name="iiTcS"></a>
### 算法
**AND 和 NOT**<br />为了区分出现一次的数字和出现三次的数字，使用两个位掩码：`seen_once `和 `seen_twice`。<br />思路是：
- 仅当 `seen_twice` 未变时，改变 `seen_once`。
- 仅当 `seen_once` 未变时，改变`seen_twice`。
位掩码 `seen_once` 仅保留出现一次的数字，不保留出现三次的数字。
<a name="CvnWR"></a>
### 实现
![](https://cdn.nlark.com/yuque/0/2021/png/2728415/1614846021633-cfa9d868-c887-4f34-a145-c712de848d8c.png#align=left&display=inline&height=300&margin=%5Bobject%20Object%5D&originHeight=944&originWidth=1692&size=0&status=done&style=none&width=538)
```cpp
seen_once=seen_twice=0;
while(){
    seen_once=~seen_twice & (seen_once ^ x);    /* seen_twice未变时，改变seen_once */ 
    seen_twice=~seen_once & (seen_twice ^ x);
}

复杂度分析

• 时间复杂度:
• 空间复杂度:

题目标题难度划分

算法掌握难度程度划分