异或运算的应用

逃离我推掉我的手 2022-11-13 15:25 193阅读 0赞

# 一、基础知识 #

异或运算，相异为1。

异或运算是一种常用的位运算，在算法题中，对于避免额外的空间复杂度有独特的用处。

异或运算也被称为“**无进位相加**”，它具有以下特性：

> 特性1：0 ^ N = N
> 
> 特性2：N ^ N = 0
> 
> 特性3（交换律）：a ^ b = b ^ a
> 
> 特性4（结合律）：(a ^ b) ^ c = a ^ (b ^ c)
> 
> 特性3 和 4总结起来，就是同一批数，不论使用怎样的顺序，怎样的结合方式进行异或，其结果始终一样。

# 二、算法题 #

**题目1**：如何不使用额外空间交换两个数？

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

推导：

a = a ^ b;
    b = a ^ b = (a ^ b) ^ b = a;
    a = a ^ b = (a ^ b) ^ a = b;

**题目2**：一个数组中有一种数出现了奇数次，其他数都出现了偶数次，找到并打印这个出现了奇数次的数。

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

解析：看到题目时，如果没有想到异或，可能会使用 HashMap 来进行词频统计，但这样就会开辟额外空间，而使用异或的方式可以轻松避免额外空间。这里用到了特性1和特性2。

**题目3**：如何把一个int数，最右侧1提取出来？例如：01101110010000，提取最右侧的 1 ，得到 0000000010000。

public static int mostRightOne(int num) {
        // 另外，num 的相反数是 -num，也等于 (~num) + 1。
        return num & ((~num) + 1);
    }

解析：~num 代表 num 按位取反。~num + 1 不仅可以得到某整数最右边的1，同时，它也代表 -num，例如，若 num = 7，那么~num + 1 = -7。因此上面代码也可以写成 num & (-num)。

**题目4**：一个数组中有两种数出现奇数次，其他数都出现了偶数次，怎么找到并打印这两种数。

分析：有两种数出现了奇数次，那么 a != b ，用 eor 变量遍历异或整个数组，那么最后结果一定是 a ^ b。且 a!= b，那么 a^b != 0，那么 eor 就一定会在某个位置上是 1 。可以利用题目三中最右1的方法得到一个最右1。**假设** eor 右边第三位是 1，那么就代表 a 的右第三位和 b 的右第三位一定是不一样的。那么数组中的所有的数就可以分成两类：第3位是1的数、第3位是0的数。那么a 和 b 一定是分开在这两类里的。

而由于整个数组异或的结果是 a ^ b ，整个数组又可以分为以 a 和 b 为代表的第3位是1的数、第3位是0的数 两类数，那么在各自的一类中，除了a 、b 之外，其他数一定是出现偶数次。那么就可以是以“第3位 是1的数”为条件，将数组重新异或一遍得到 eor1，假设 a 就属于 “第3位是1的数”这一类，那么eor1 = a，最后，eor ^ eor1 = b。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3NDUwNjk_size_16_color_FFFFFF_t_70][]

public static void printOddNum2(int[] arr) {
        int eor = 0;
        // eor = a ^ b != 0
        for (int i = 0; i < arr.length; i++) {
            eor ^= arr[i];
        }
        // eor 最右1
        int mostRightOne = eor & (-eor);
        int eor1 = 0;
        for (int i = 0; i < arr.length; i++) {
            if ((arr[i] & mostRightOne) != 0) {
                eor1 ^= arr[i];
            }
        }
        // eor1 = a
        int a = eor1;
        int b = eor ^ eor1;
        System.out.println("a = " + a + ", b = " + b);
    }

**题目5**：一个数组中有一种数出现了K次，其他数出现了M次，M>1,  K < M ，找到出现 K 次的数，要求额外空间复杂度是O(1)，空间复杂度O(N)。

解析：看到 “额外空间复杂度是 O(1)” ，基本上就可以把哈希表的方式排除了，最好的实现方向就是使用异或。解题的关键思路是 K < M 这个条件，如果数组中的每个数都表示为一个2进制数列，那么如果将所有数按位累加（注意是按位累加，不是按位相加），那么每个二进制位置上要么是M的整数倍，要么是M的整数倍加K。因此，将累加结果按位取余就可以得到该出现K次的数，例如：0K00KK00KKK0K00，最后因为不是求K，只要求返回该数，因此K= 1也无妨。

public static int KM(int[] arr, int K, int M) {
        int[] bit = new int[32];
        for (int num : arr) {
            for (int i = 0; i < bit.length; i++) {
                // 注意这里一定不能写成：num & (1 << i)，比较一下两者的值就知道原因了
                bit[i] += (num >> i) & 1;
            }
        }
        int ans = 0;
        for (int i = 0; i < bit.length; i++) {
            if ((bit[i] % M) != 0) {
                ans |= (1 << i);
            }
        }
        return ans;
    }

第五题对数器：

public class KMChecker {
    
        public static int test(int[] arr, int k, int m) {
            HashMap<Integer, Integer> countMap = new HashMap<>();
            for (int i : arr) {
                if (countMap.containsKey(i)) {
                    countMap.put(i, countMap.get(i) + 1);
                } else {
                    countMap.put(i, 1);
                }
            }
            for (Integer key : countMap.keySet()) {
                if (countMap.get(key) == k) {
                    return key;
                }
            }
            return -1;
        }
    
        /**
         * [-range, +range]
         *
         * @param range
         * @return
         */
        public static int randomNum(int range) {
            return ((int) ((Math.random() * range) + 1) - (int) ((Math.random() * range) + 1));
        }
    
        public static int[] randomArr(int kinds, int range, int k, int m) {
            int kTimeNum = randomNum(range);
            // numKinds >= 2
            int numKinds = (int) (Math.random() * kinds) + 2;
    
            // k * 1 + (numKinds - 1) * m
            int[] arr = new int[k + (numKinds - 1) * m];
    
            int index = 0;
            for (; index < k; index++) {
                arr[index] = kTimeNum;
            }
            numKinds--;
            HashSet<Integer> set = new HashSet<>();
            set.add(kTimeNum);
            while (numKinds != 0) {
                int curNum = 0;
                do {
                    curNum = randomNum(range);
                } while (set.contains(curNum));
                set.add(curNum);
                numKinds--;
                for (int i = 0; i < m; i++) {
                    arr[index++] = curNum;
                }
            }
            // arr填好了
            for (int i = 0; i < arr.length; i++) {
                // i 位置的数，我想随机和j位置上的数交换
                int j = (int) (Math.random() * arr.length);
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
            return arr;
        }
    
        public static void main(String[] args) {
            int kinds = 10;
            int range = 200;
            int testTime = 100000;
            int max = 9;
            for (int i = 0; i < testTime; i++) {
                int a = (int) (Math.random() * max) + 1; // a 1~9
                int b = (int) (Math.random() * max) + 1; // b 1~9
                int k = Math.min(a, b);
                int m = Math.max(a, b);
                // k < m
                if (k == m)
                    m++;
                int[] arr = randomArr(kinds, range, k, m);
                // 对照组
                int ans1 = test(arr, k, m);
                // 测试方法
                int ans2 = 异或运算.KM(arr, k, m);
                if (ans1 != ans2)
                    System.out.println("错误！");
            }
        }
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3NDUwNjk_size_16_color_FFFFFF_t_70]: /images/20221022/ea5aa40e91e6433c93670f02f29178e6.png