异或运算

基本概念

1. 异或运算：想同为0，不同为1
2. 同或运算：想同为1，不同为0

即无进位相加

性质

1. 0^N == N N^N == 0
2. 异或运算满足交换律和结合率

即：a^b = b ^ a

(a^b)^c=a^(b^c)

题一、如何不同额外变量交换两个数

int a = a ^ b

int b = a ^ b

int a = a ^ b

题二、一个数组中有一种数出现奇数次

//arr中，只有一种数出现奇数次，其他都是偶数次,打印
public static void printOnceNum(int[] arr){
    int eor = 0;
    for (int i = 0; i < arr.length; i++) {
        eor ^= arr[i];
    }
    System.out.println(eor);
}

题三、怎么把int类型的数，最右侧1提取出来

int rightOne = a & (-a) 

题四、一个数组中有两种数出现奇数次

//arr中，有两个数出现奇数次，其他数出现偶数次
public static void printTwiceNum(int[] arr){
    int eor = 0;
    for (int i = 0; i < arr.length; i++) {
        eor ^= arr[i];
    }
    int rightOne = eor & (-eor);
    int onlyOne = 0;
    for (int i = 0; i < arr.length; i++) {
        if ((arr[i]&rightOne)!=0){
            rightOne ^= arr[i];
        }
    }
    System.out.println(rightOne+" "+(eor ^ rightOne));
}

题五、一个数组中一种数出现k次，其他M次

//一个数组中有一种数出现K次，其他数都出现M次
//M>1,K<M
//找到出现K次的数
//要求额外空间复杂度O(1)，时间复杂度O(N)
//普通方法
public static int getKTimesNum(int[] arr,int K,int M){
    HashMap<Integer,Integer> map = new HashMap<>();
    for (int num:arr) {
        if (!map.containsKey(num))
            map.put(num,1);
        else
            map.put(num,map.get(num)+1);
    }
    for (Integer key:map.keySet()) {
        if (map.get(key) == K)
            return key;
    }
    return -1;
}
//使用位运算
public static int getKTimesNum2(int[] arr,int K,int M){
        int[] count = new int[32];
        for (int num : arr){
            for (int i = 0; i < 32; i++) {
                //两种表示方式
//                if ((num & (1<<i)) != 0){
//                    count[i]++;
//                }
                count[i] += (num >> i) & 1;
            }
        }
        int ans = 0;
    //两种表示方式
//        for (int i = 0; i < count.length; i++) {
//            count[i] = (count[i]%M)/K;
//        }
//        for (int i = 0; i < count.length; i++) {
//            ans |= (count[i] << i);
//        }
        for (int i = 0; i < count.length; i++) {
            if (count[i]%M !=0)
                ans |= (1 << i);
        }
        return ans;
    }