題目要求:

一個整型數(shù)組里除了兩個數(shù)字之外管怠，其他的數(shù)字都出現(xiàn)了兩次反症。請寫程序找出這兩個只出現(xiàn)一次的數(shù)字

看到有同學(xué)做了“選取奇數(shù)個數(shù)的數(shù)字”的題目殖熟，但是題目為
“一個整型數(shù)組里除了一個數(shù)字之外牵舵，其他的數(shù)字都出現(xiàn)了兩次悍引。請寫程序找出這兩個只出現(xiàn)一次的數(shù)字”
可以采用排序的方法求解妒蛇，讓數(shù)字成對出現(xiàn)机断，但是排序的算法最優(yōu)時間復(fù)雜度是 O(nlog2n)，也可以采用異或求解绣夺，利用異或的方法吏奸，可以讓相同的兩個數(shù)字相互異或消除，達(dá)到求解目的陶耍。
例：a[100] = {7,1,2,3,1,2,3,4,4}

#include "stdio.h"

int number(int a[], int n) {
    int i;
    int result = 0;
    for (i = 0; i<n;i++) {
        result ^= a[i];
    }
    return result;
}

int main(void) {
    int a[100] = {7,1,2,3,1,2,3,4,4};
    printf("%d\n",number(a, 9));
}

但是如果結(jié)果有兩個只出現(xiàn)一次的數(shù)字時奋蔚，又該如何求解？
例：a[100] = {7,6,1,2,3,1,2,3,4,4}
結(jié)果會出現(xiàn)7和6的位相與后的結(jié)果 1烈钞，而不是7和6泊碑。

做題思路:

按照正常思路最終結(jié)果是求出a^b的值，為了求那兩個奇數(shù)個的數(shù)毯欣，可以通過a = (a^b) ^ b 和 b = (a^b) ^ a來求解a和b馒过， （a ^ b）已知，剩下的就是通過(a ^ b)想辦法求出a和b的數(shù)字了酗钞。
①：求（a ^ b）
②：利用（a ^ b）求a腹忽，b
例中數(shù)組{7,6,1,2,3,1,2,3,4,4}求得的（a ^ b）為 7^6来累，二進(jìn)制表示為0111和0110，所以（a ^ b）的結(jié)果會求得0001窘奏，然后我們要通過0001來分析嘹锁。
首先出現(xiàn)位為1的可能就是位不相等異或出來的，可以將數(shù)組分為兩個子數(shù)組着裹，我們把原數(shù)組分成了兩個子數(shù)組兼耀，每個子數(shù)組都包含一個只出現(xiàn)一次的數(shù)字，而其他數(shù)字都出現(xiàn)兩次求冷。
如：a[100] = {7,6,1,2,3,1,2,3,4,4} 可變成{0111,0110,0001,0010,0011,0001,0010,0011,0100,0100}
分成兩個子數(shù)組分別為a = {, 000,001,000,001}（通過（a ^ b）= 0001獲得所有結(jié)尾為的數(shù)）和b = {,0010,0010,0100,0100}，將子數(shù)組內(nèi)元素相異或窍霞，即求得a和b

#include "stdio.h"
//獲得（a ^ b）上的第一個位為1的位置
int FindFirstBitls1(int num) {
    int indexBit = 0;
    while ((num & 1) == 0) {
        num = num >> 1;
        ++ indexBit;
    }
    return indexBit;
}
//判斷數(shù)組中的元素是否指定的位為1
_Bool IsBit1(int num, int indexBit) {
    num = num >> indexBit;
    return (num & 1);
}

void number(int array[], int n, int a, int b) {
    int i,j;
    int result = 0;
    for (i = 0; i<n;i++) {
        result ^= array[i];
    }
    int indexOf1 = FindFirstBitls1(result);
   a = b = 0;
    for (j = 0; j<n; ++j) {
        if(IsBit1(array[j], indexOf1))     //位為1匠题，存入a數(shù)組
            a ^= array[j];
        else                               //否則，存入b數(shù)組
            b ^= array[j];
    }
    printf("%d\n",a);
    printf("%d\n",b);
}

int main(void) {
    int array[112] = {6,1,2,3,1,2,3,4,4,7};
    int a,b;
    number(array, 10, a, b);
}