1.题目:给定一个含有n个元素的整型数组arr,其中只有一个元素出现奇数次,其余的都出现偶数次,找出这个元素。
思路:我们基本上都知道计算机的位运算,其中有一个异或运算:对于任意一个数k,k^k=0,k^0=k,所以我们只需要将arr中所有的元素进行异或,那么个数为偶数的元素异或后都变成了0，只留下那个个数为奇数的那个元素。

#include <stdio.h>
void Find(int arr[], int len) {
    int s = 0;
    for (int i = 0; i < len; i++)
        s ^= arr[i];
    printf("%d\n", s);
}
int main() {
    int len = 9, arr[9] = {1, 2, 3, 5, 7, 1, 3, 5, 7};
    Find(arr, len);
    return 0;
}

2.题目:给定一个含有n个元素的整型数组arr,其中有两个元素出现奇数次,其余的都出现偶数次,找出这两个元素。
思路:我们假设这两个数分别为a、b,并将数组元中所有元素异或之后的结果为s。因为a!=b,所以s=a^b且s!=0,判断s的二进制中为1的位数。我们只需要知道s某一为1的位数k(如00101010,其中1对应的位数分别为1、3、5,所以k可以取1、3或5),然后将s与数组中第k位为1的元素进行异或,异或结果就是a或b其中的一个,然后用s与其异或,即可得出另外一个。因为s中的第k位为1,表示a或b中其中一个的第k位也为1,假设为a,将s与数组中第k位为1的元素进行异或时,即将s与a以及其它第k位为1的出现过偶数次的数进行异或,化简即为s与a异或,最终结果即为b。

#include <stdio.h>
void Find(int arr[], int len) {
    int s = 0;
    for (int i = 0; i < len; i++)
        s ^= arr[i];
    int s1 = s, s2 = s, k = 0;
    while (!(s1 & 1)) {
        s1 >>= 1;
        k++;
    }
    for (int i = 0; i < len; i++)
        if ((arr[i] >> k) & 1)
            s ^= arr[i];
    printf("%d %d\n", s, s ^ s2);
}
int main() {
    int len = 10, arr[10] = {1, 2, 3, 5, 7, 1, 3, 4, 5, 7};
    Find(arr, len);
    return 0;
}