位运算,二进制，异或的一些算法题

好记性不如烂笔头
一，异或用法：
1.不借用变量前提，交换两数值？

a = a ^ b;
b = a ^ b;
a = a ^ b;

2.数组中只有一个数出现奇数次，其余数都出现了偶数次，怎么找到这个数？

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

3.提供有一个int数，提取其最右侧第一个1 （a&（~a+1））
记住定律 a&(-a) 结果是右侧第一个数为1，其余为0的数（二进制）
4.一个数组有两个数出现奇数次，其他都出现偶数次，求这两个数（需要需用2，3的结论）

//假设a,b为这两个奇数次数，原理就是先异或，求出结果eor = a^b
//可以得出结论eor必定不为0，说明二进制位必定有一位为1
//找到最右侧1的位rightOne利用3.的知识点
//可以得出结论a,b必定分属两个阵营，如果a的rightOne为1，那么b的肯定为0
//同理剩余的出现的偶数次的数他们也可以被分成这两个阵营
//再利用a去异或自己阵营的这些偶数次的数可以得到a=eor`，b则等于eor^eor`
public static void findTwo(int[] arr){
    int eor = 0;  //eor其实就是a^b
    for(int i=0;i< arr.length;i++){
        eor ^=arr[i];
    }
    int rightOne = eor&(-eor);
    int onlyOne = 0 ; //eor'
    for(int i=0;i<arr.length;i++){
        if((arr[i]&rightOne)!=0){  //说明arr[i]和rightOne的1重叠到了，就可以划出阵营
            onlyOne ^= arr[i];
        }
    }
    System.out.println("一个是"+onlyOne+"另一个是"+(onlyOne^eor));
}

5.一个数组中有一个数出现了K次，其他数出现了M次，已知M>1,K<M，求出出现K次的数的值，要求空间复杂度O(1),时间复杂度O(n)

/**
 解题思路：整型数int是32位字节的，我们开辟一个长度为32的数组，里面暂时全放0
 然后将出先K次的数二进制上出现了1的位置加到数组里面，同理M也将二进制位出现了1的数加到数组
 最后出现的数组可能就类似[...a],假设数组最后一位等于a,说明a的组成成分可能有K也可能有M
 如果有K，那么用a%M则必不可能=0，同理，如果a%M=0说明此处K的二进制位0，
 则我们就可以根据求余%运算推导出最后的k的二进制表示从而算出K为多少
 */
public static void findK(int[] arr,int k,int m){
    int[] a = new int[32];    //定义32位的数组
    for(int num : arr){               
        for (int i = 0; i < 32; i++) {         //这个是常数次循环，所以是O(1)
            if(((num>>i)&1)!=0){           //这里((num>>i)&1)!=0说明num第i位上的数是1
                a[i]++;                    //可以写成a[i]+=((num>>i)&1),就不需要if语句
            }
        }
    }
        int answer = 0;                 //结果值
        for(int i=0;i<32;i++){ 
            if(a[i]%m!=0){             //求余，如果不等于0说明此处K有1
                answer |=(1<<i);         //则将1左移i位平且和answer做或运算，并且并入answer中
            }                            //循环32次结束后，1都填上后就是k的二进制值表示方法
        }
        System.out.println(answer);
    }