【算法&数据结构体系篇class02】：异或运算技巧

￡神魔★判官ぃ 2024-03-27 17:25 48阅读 0赞

package train;
    
    public class EvenTimesOddTimes {
        // arr中，只有一种数，出现奇数次   运用异或运算 自身偶数个异或值为0的特点来处理
        public static void printOddTimesNum1(int[] arr) {
            int eor = 0;
            for(int i = 0; i<arr.length;i++){
                eor ^= arr[i];
            }
            System.out.println(eor);
        }
    
        // arr中，有两种数a,b，出现奇数次  异或后结果就是a^b的结果 再利用这个位运算技巧来拆分两个数
        public static void printOddTimesNum2(int[] arr) {
            int eor = 0;
            for(int i= 0;i<arr.length;i++){
                eor ^= arr[i];
            }
            //a^b接着就是把异或的值，两数不一样就代表肯定存在某一位为1 异或就是不同为1，表示这一位一个是1 另一个是0 取出最右侧的1，然后再将这个值
            //与每个值进行 与运算， 这样与完 为1的就是a或者b了
            //取出最右侧位1 其余位为0的一个值
            int rightOne = eor & (-eor);
            //接收一个数a
            int a = 0;
            for(int i = 0;i<arr.length;i++){
                if((arr[i] & rightOne) != 0){
                    a ^= arr[i];
                }
            }
            //另外一个数b 就可以用前面eor的值异或a,因为eor= a^b  再^b就等于b
            int b = eor ^ a;
            System.out.println("奇数为"+ a+"---"+b);
        }
    
        // 输入一定能够保证，数组中所有的数都出现了M次，只有一种数出现了K次
        // 1 <= K < M
        // 返回这种数
        public static int km(int[] arr, int k, int m) {
            //定义一个整形数组来存放全部数组元素二进制，将每一个进制位为1的进行累加
            int[] temp = new int[32];
            for(int num: arr){
                for(int i = 0;i<32;i++){
                    temp[i] += ((num>>i)&1);
                }
            }
            //接收k个元素的结果值
            int ans = 0;
            for(int i = 0; i< 32;i++){
                //其余数都是m个，如果元素出现m次，当前二进制位是1，那么求模肯定是等于0，
                // 不为0，说明出现k次的元素当前二进制位为1
                temp[i] %= m;
                if(temp[i] != 0){
                    //不为0 说明该位1是出现k次的元素，则用或运算，把1加到ans结果值上
                    ans |= 1<<i;
                }
            }
            return ans;
        }
    
        //判断一个数的二进制中有多少个1
        public static int bit1counts(int N) {
            int count = 0;
            while(N != 0){
                //取出一个二进制，是最右侧为1的二进位
                int rightOne = N & (-N);
                //N 异或 最右侧为1的而二进制数， 就相当于减去最右侧1 剩余的值
                N ^= rightOne;
                //计数器+1
                count++;
            }
            return count;
        }
    
    
        public static void main(String[] args) {
            int a = 5;
            int b = 7;
    
            a = a ^ b;
            b = a ^ b;
            a = a ^ b;
    
            System.out.println(a);
            System.out.println(b);
    
            int[] arr1 = { 3, 3, 2, 3, 1, 1, 1, 3, 1, 1, 1 };
            printOddTimesNum1(arr1);
    
            int[] arr2 = { 4, 3, 4, 2, 2, 2, 4, 1, 1, 1, 3, 3, 1, 1, 1, 4, 2, 2 };
            printOddTimesNum2(arr2);
    
        }
    }