算法 | 如何用位运算从一堆数中寻找出现奇数次的数？

前言

本文主要介绍如何使用位运算从一堆数中寻找出现奇数次的数，这一堆数中有很多数出现了偶数次，只有一个数出现了奇数次，那么该如何寻找出这个数呢？

如果不使用位运算的话，我们可以用一个Map记录下每个数出现的次数，判断次数是奇数还是偶数就行了，但现在要求使用位运算该怎么办呢？

思路分析

假如有一组数，arr = [1, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4]，其中只有1出现了奇数次，其他的数都出现了偶数次，那我们的目的就是把1给找出来。

使用位运算的话，要使用到异或运算，异或运算就是如果两个数相同的话，那么两个数的运算结果为0，关于具体的运算规则可以参考这篇文章，使用位运算交换两个数。

先看下异或运算的基本规则：

0 ^ 0 = 0 
0 ^ N = N 
N ^ 0 = N 
N ^ N = 0

根据异或运算的规则，我们可以看到，两个相同的数进行异或的话结果为0，而0与另一个数进行异或的话，结果为另一个数本身。

根据异或运算的这个特性，我们就可以把数组中的每一个数都进行异或运算，这样的话，出现偶数次的数必定会被拆成N组两个相同的数，所以数组中偶数所有数参与的结果为0，这样就得到了奇数次的数。

以arr = [1, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4]为例，我们来看下运算过程。

1. 1参与异或运算，R1 = 1 ^ 1 ^ 1 = 1 ^ 1 = 1。
2. 2参与异或运算，R2 = 2 ^ 2 = 0。
3. 3参与异或运算，R3 = 3 ^ 3 ^ 3 ^ 3 = 0 ^ 3 ^ 3 = 3 ^ 3 = 0。
4. 4参与异或运算，R4 = 4 ^ 4 ^ 4 ^ 4 = 0 ^ 4 ^ 4 = 4 ^ 4 = 0。
5. 最后结果运算，R = R1 ^ R2 ^ R3 ^ R4 = 1 ^ 0 ^ 0 ^ 0 = 1。

经过以上步骤，就可以得出结论，数组中1出现了奇数次。

代码实现

public class Code15_OddTimesNum {

    public static void main(String[] args) {
        int[] arr = {1, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4};
        int res = find(arr);
        System.out.println(res);
    }

    public static int find(int[] arr) {
        int res = 0;
        for (int i = 0; i < arr.length; i++) {
            res ^= arr[i];
        }
        return res;
    }
}

运行结果为1。

可以看到在使用位运算时，只声明了一个临时变量，只需执行一次for循环就可以了。

如果用Map的话，还得再遍历一次Map，对比位运算来说，性能就有些低了。

总结

本文主要介绍如何使用位运算从一堆数中寻找出现奇数次的数，主要是利用异或运算相同为0的特性实现了这个功能。

如果你有更好的办法，欢迎在评论区留言一起交流~