异或运算符

定义与理解

异或运算，相同为0，不同为1。

可以理解成不进位加。

• 交换律：a ^ b = b ^ a
• 结合律：(a ^ b) ^ c = a ^ (b ^ c)

应用

找出不同数字

题目：一个数组，有n种数出现偶次，只有一种数出现奇次，找出奇次的这种数。

eor=0，遍历数组从头亦或到位，得到的数就是奇次的这种数。

O(n)、S(1) 方法

把相同的数都异或掉，剩余的数就是。

package learn.note.algorithm.bit;

/**
 * @author Wang WenLei
 * @date 2025/7/23 16:57
 * @since 1.0
 */
public class FindOne {
    public static void main(String[] args) {
        int [] data = {11,12,13,14,15,6,14,13,12,11,15};
        int res = findOne(data);
        System.out.println(res);
    }

    public static int findOne(int [] data){
        int low = 0;
        // 使用异或，满足条件，则两个数相同，异或结果为0
        for (int datum : data) {
            low = low ^ datum;
        }
        return low;
    }
}

找出不同的2个数字

题目：一个数组，有n种数出现偶次，只有两种不同的数出现奇次，找出奇次的这两种数。

O(n)、S(1) 方法

package learn.note.algorithm.bit;

/**
 * @author Wang WenLei
 * @date 2025/7/23 16:57
 * @since 1.0
 */
public class FindOne {
    public static void main(String[] args) {
        int [] data = {11,12,13,14,4,6,14,13,12,11};
        int[] two = findTwo(data);
        System.out.println(two[0]+"--"+two[1]);
    }

    public static int[] findTwo(int [] data){
        int eor = 0;
        // 假设两个不同的奇个数的数是a、b，得到 eor = a ^ b
        for (int datum : data) {
            // 使用异或，满足条件，则两个数相同，异或结果为0
            eor = eor ^ datum;
        }
        // 找到最右边的1
        int rightOne = eor & (~eor + 1);
        int lowEor = 0;
        for (int cur : data) {
            // 这里有讲究，& 后只得到最右边1的数或0两种情况。用来筛选出两类数
            if ((cur & rightOne) == 0) {
                lowEor = lowEor ^ cur;
            }
        }
        return new int[]{eor ^ lowEor, lowEor};
    }
}