本文主要是介绍使用异或查找数组中出现奇数次的唯一或唯二数字，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
1.查找数组中的所有出现奇数次的数字，要求数组中不能有负数
2.现在有个数组，假设这个数组中出现奇数次的数字有且只有1个，请把它找出来
3.现在有个数组，假设这个数组中出现奇数次的数字有且只有2个，请把它找出来
先看题1的：
以下代码用c实现,由于c语言中没有字典,也不想上升到c++,所以实现起来较为复杂，可以不看，直接看下面的异或算法
#include<stdio.h>
#include <stdlib.h>struct MyStruct
{int* arr;int arr_size;
};int cmpfunc(const void* a, const void* b)
{return (*(int*)a - *(int*)b);
}
struct MyStruct find_odd_occurrence(int a[], int n) {//查找数组中的所有出现奇数次的数字，要求数组中不能有负数//先对数组a进行排序qsort(a, n, sizeof(int), cmpfunc);int last_num = - 1;int* res = (int*)malloc(n * sizeof(int));int res_index = 0;for (int i = 0; i < n; i++) {if (last_num == a[i]) {continue;}else {last_num = a[i];}int count = 1;for (int j = i + 1; j < n; j++) {if (a[j] == a[i]) {count += 1;}}if (count % 2 == 1) {res[res_index] = a[i];res_index += 1;}}//重新申请一个数组把多余的数字去掉int* res_arr = (int*)malloc(res_index * sizeof(int));for (int x = 0; x < res_index; x++) {res_arr[x] = res[x];}free(res);struct MyStruct real_res;real_res.arr = res_arr;real_res.arr_size = res_index;return real_res;
}int main() {int b[8] = { 1,2,2,9,4,4,5,5 };struct MyStruct res = find_odd_occurrence(b, 8);for (int k = 0; k < res.arr_size; k++) {printf("%d\n", res.arr[k]);}free(res.arr);return 0;
}如上，经历了排序，2层for循环再遍历查找计数，再遍历计数为奇数项的数字，再处理结果，得到了一个通用的获取数组中所有出现奇数次的函数。
再看题2的
#include<stdio.h>int find1odd(int a[], int n) {//要求数组a中只有一个数字出现奇数次，则本函数能快速查找到数组中的这个数int res = 0;for (int i = 0; i < n; i++) {res ^= a[i];}return res;
}int main() {int a[11] = { 1,1,2,2,2,3,2, 3,4,3,3 };printf("%d\n", find1odd(a, 11));return 0;
}
异或的规则：
（1）相同为0，相异为1
(2) 异或满足交换律，即 a ^ b ^ c = a ^ ( b ^ c) = a ^ c ^ b
(3) N ^ N = 0, N ^ 0 = N;
解读：
数组中出现偶数次的数字异或后通通为0，类似消消乐可以直接划掉，最后只剩下了出现奇数次的数字。
然后我们再看看第三题的
#include<stdio.h>int or2(int a[], int n) {//假设数组a中只有2个数字出现奇数次int res = 0;for (int i = 0; i < n; i++) {res ^= a[i];}return res;
}int find_right1(int n) {//查找一个数最右边的1，如0b000001100,返回0b000000100return n & (~n + 1);
}int get1fromgroup(int a[], int n, int right1) {//原理是进行2分组，一组和right1中1的位置同样是1，一组是0int res = 0;for (int i = 0; i < n; i++) {if (a[i] & right1) {res ^= a[i];}}return res;
}int main() {int b[8] = { 1,2,2,9,4,4,5,5};int two_or = or2(b, 8);int right1 = find_right1(two_or);int one_odd = get1fromgroup(b, 8, right1);int other_odd = two_or ^ one_odd;printf("%d, %d", one_odd, other_odd);return 0;
}
解读：
数组中出现偶数次的数字异或后直接消失，只剩下2个奇数异或的值，表示为 two_or = x ^ y
假设这个two_or = b00001101,根据相异为1，我们分析1出现的位置x和y只能有一个贡献了1，那么我们可以根据其中任意一位的1对所有数组中的数字进行分组，即此位是1还是0进行分组，那么x和y必然分别出现两个分组里， 然后其它数字不管此位是0还是1，全部是出现了偶数次，所以不管分在那个分组，经过异或后全部抵消掉了。
这里我们选择的是出现在最右侧的1，这里有个小技巧
即 查找一个数最右边的1，可以通过 n & (~n + 1)得到，如获取整数6的最右侧的1
0b0000 0110
取反得到0b1111 1001
再+1得到0b1111 1010
&后 得到 0b0000 0010
（&的规则是两个都为1（真）则1（真），其它全部为0（假））
这篇关于使用异或查找数组中出现奇数次的唯一或唯二数字的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
