数组中数字出现的次数

发表于 | 浏览 次

数组中只出现一次的数

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
题目来源：剑指offer 56

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
unsigned int findFirstBitIs1(int num) {
    int indexBit = 0;
    while (((num & 1) == 0) && (indexBit < 8 * sizeof(int))) {
        num = num >> 1;
        ++indexBit;
    }
    return indexBit;
}

bool IsBit1(int num, unsigned int indexBit) {
    num = num >> indexBit;
    return (num & 1);
}

void findNumsAppearOnce(vector<int> data, int *num1, int *num2) {
    if (data.size() < 2) {
        return;
    }
    int resultExclusiveOR = 0;
    for (int i = 0; i < data.size(); i++) {
        resultExclusiveOR ^= data[i];
    }
    unsigned int indexOf1 = findFirstBitIs1(resultExclusiveOR);
    *num1 = *num2 = 0;

    for (int i = 0; i < data.size(); i++) {
        if (IsBit1(data[i], indexOf1)) {
            *num1 ^= data[i];
        } else {
            *num2 ^= data[i];
        }
    }
}