位运算基础——找出数组中唯一一个只有一个的数

留言

简单模式：数组中只有一个数出现一次，其他均出现两次，请找出这个数。

1
2
3
4
5
6
7
8
//原理：a ^ a = 0   a ^ 0 = a
int FindOnlySum(vector<int>& nums){
    int result = 0;
    for(auto& num : nums){
        result ^= num;
    }
    return result;
}

进阶模式：数组中只有一个数出现一次，其他均出现三次，请找出这个数。(题目来自力扣137)

例：
【1，2，3，2，4，4，3，4，2，3】
0001
0010
0011
0010
0100
0100
0011
0100
0010
0011
++++
0364
%%%%3
0001

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//
int FindOnlySum(vector<int>& nums){
    int ans = 0;
    for (int i = 0; i < 32; ++i) {
        int total = 0;
        for (int num: nums) {
            total += ((num >> i) & 1);//(num >> i) & 1 -> num左移i位，然后与1与  == 取num的第i位
        }
        if (total % 3) {  //total % 3 = 0 / 1
            ans |= (1 << i);  // ans | (1 << i) -> 1右移i位，与ans或 == 将ans的第i位变成1
        }
    }
    return ans;
}

算法改进

第i位(ai,bi)初始(00)连续经过三个零或三个1又变回(00)

(00)->(01)->(10)->(00)

(ai,bi) xi 新(ai,bi)
00 0 00
00 1 01
01 0 01
01 1 10
10 0 10
10 1 00

a = (~a & b & x) | (a & ~b & ~x)
b = ~a & (b ^ x)

最后结果:ai=0 ,bi=0/1,即返回b即可。

1
2
3
4
5
6
7
int FindOnlySum(vector<int>& nums) {
    int a = 0, b = 0;
    for (int num: nums) {
        tie(a, b) = pair{(~a & b & num) | (a & ~b & ~num), ~a & (b ^ num)};
    }
    return b;
}

进一步改进–同时计算改为分步计算

因为bi计算更简单，所以我们先计算bi,再用新bi计算ai。
(00)->(01) => (00)->(01)->(01)

(ai,bi) xi 新bi
00 0 0
00 1 1
01 0 1
01 1 0
10 0 0
10 1 0
(新ai,bi) xi 新ai
00 0 0
01 1 0
01 0 0
00 1 1
10 0 1
10 1 0

b = ~a & (b ˆ x)
a = ~b & (a ˆ x)
​

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int FindOnlySum(vector<int>& nums) {
        int a = 0, b = 0;
        for (int num: nums) {
            b = ~a & (b ^ num);
            a = ~b & (a ^ num);
        }
        return b;
    }
};