算法题（24）：只出现一次的数字（二）

审题：

数组中除了答案元素只出现一次外，其他元素都会出现三次，我们需要找到并返回答案元素

思路：

由于现在会出现三次，所以利用异或运算符的方法就会失效。而所有数据都在32位二进制范围内，所以我们采用依次确定二进制位的方法来计算

方法：依次确定二进制位

对于只出现一次的数据，它的第i位二进制数可能是0或1.

对于出现三次的数据，它的第i位二进制数据可能是0/1，但是若将他们加起来就一定是3的倍数（0或3）

而如果我们对数组中所有元素第i位二进制数的和除以3并取余数就可得到答案第i位的二进制数,然后将这位给到答案上即可

解题：

外层循环：目的是进行不同位数答案的计算与赋值

内层循环：将nums数组所有元素的第i位（i从0开始）加起来给到total

if语句：当余数是1说明我们答案在当前位数的二进制数是1，需要把1给到答案的第i位

若余数不是1，说明我们答案在当前位数的二进制数是0，由于我们答案初始化为0（相当于32为二进制数都是0），所以0就不用我们去赋值了

关键代码：

1.如何得出第i位二进制数的值？

首先把数据右移i位，然后利用位与运算和1进行运算

因为1的前面31位都是0，所以不管e前面31位是多少，最后都会变成0。也就是需要比较的只有第32位，我们把第i位都移动到32位，如果该位大小为1，那么和1进行位与操作就可以得出结果为1，否则为0.这样就实能将对应位大小提取出来

2.如何将答案的第i位赋值为1？

首先把1左移i位，然后与答案进行位或运算

因为1左移i位后，其他位数都为0，位或操作的性质决定了我们不会改变答案的其他位的值。

此时因为答案第i位是0，而我们左移后的“1”的第i位是1了，根据位或性质，第i位运算出来就是1，又因为其他位不变，所以成功在答案其他位不变的情况下实现了赋值1

补充：

位与运算符：&

当两个二进制数对应位的值都是1，那么运算得出1，否则为0

eg：0011 & 1100 -》0000

位或运算符：|

当两个二进制数对应位的值有一个是1，那么就得出1，否则为0

eg：0011 & 1100 ——》1111

137. 只出现一次的数字 II - 力扣（LeetCode）