ASCII码 ASCII码

算法之异或操作

发布于：2022-01-17 09:20:14  栏目：技术文档

异或操作0 ^ 0 = 00 ^ 1 = 11 ^ 0 = 11 ^ 1 = 0异或操作可以看做无进位相加操作也就是两个数相加，但是只做加法，不进位。

  1.  1110101 
  2. ^1011011 
  3. ---------- 
  4.  0101110

运算定律0^a = a, a^a = 0满足交换律 a^b = b^a满足结合律 (a^b)^c = a^(b^c)一堆数异或，无论顺序如何，结果相同，其实就是上面的结合律。

下面来看两道题：例1数组中有一列数字，其中有一个数字a出现了奇数次，其他的数字出现的次数都是偶数次，求出数字a,要求时间复杂度是O(n),空间复杂度是O(1)。分析：假设这列数字是aaabbccdddd，顺序无所谓，把这些数字进行异或操作，根据第一个定律，两个相同的数字进行异或后是0，重复出现次数为偶数次的数进行异或后都是0，剩下的3个a，其中两个异或后也是0，剩下的就是a，所以也就是说把数组遍历一遍，进行异或操作，最终结果就是要求的数字a。

  1.    public static int getOddTimesNumber(int[] arr) {
  2.         int res = 0;
  3.         for (int i: arr) {
  4.             res ^= i;
  5.         }
  6.         return res;
  7.     }

例2数组中有一列数字，其中有两个数字a和b出现了奇数次(a≠b)，其他的数字出现的次数都是偶数次，求出数字a和b,要求时间复杂度是O(n),空间复杂度是O(1)。分析：1.把数组遍历一遍进行异或操作后，得到的结果记为eor，这个eor最终一定是a^b。2.如果能找到一种方法把a或者b找出来，记为x，（假设x是a）;那么eor^x就是b。利用O(1)的空间，我们是没法找的，记录频率肯定空间不够哈。那么能否将两者区分开呢？因为a和b不相等，所以eor不等于0，那么其二进制肯定有某些位置是1，或者说至少有一位是1。那么a和b的二进制在这个位置处肯定不一样（也就是说一个是1，一个是0），否则异或后eor的该位置一定是0。利用这个观察到的规律，可以把数组中的数分成两组，a在一组数中，b在另外一组数中。这里设置为一个未处理的标记，我们等会儿来解决。我们先来看一个位运算的例子：eor & (~eor + 1)eor取反加一，然后和自身进行与运算。来看看得到的结果是什么：

  1. 假设eor = 1001110001000
  2. eor: 1001110001000
  3. ~eor=0110001110111
  4. +1  =0110001111000
  5. &eor:1001110001000
  6. =    0000000001000

得到的是最右边的1保留，其余位数变为0,这个结果记为rightZero，1的位置记为index.如何利用这个数字的特性来吧a和b区分开来呢？看这个操作if ((x & rightZero) == rightZero) {…}数值x和rightZero进行与操作，就会把x的第index处保留，其他位置上清除为0。在判断语句中判断结果是否==rightZero就会检查x的index处是否为1。

用这个方法遍历数组，就可以解决上面留的问题，把a和b分开。遍历数组，用上面的判断语句，符合条件的是一堆，不符合条件的是一堆，而a和b肯定在两个堆中。把满足条件的一堆，进行异或运算，得到的肯定是a或b其中之一，而拿eor^得到的这个数，得到的就是另一个。下面来看下实现：

  1.  public static int[] getOddTimesTwoNumber(int[] arr) {
  2.         int[] resArray = new int[2];
  3.         int eor = 0;
  4.         for (int i: arr) {
  5.             eor ^= i;
  6.         }
  7.         // eor取反加一，然后和eor自身进行与运算，结果会把eor二进制格式的最右边的1保留，其余位变成0
  8.         // 1001110001000运算后是
  9.         // 0000000001000
  10.         int rightZero = eor & (~eor + 1);
  11.         int first = 0;
  12.         for (int i: arr) {
  13.             // 以此条件进行区分，把所求的两个数区分成两组，
  14.             if ((i & rightZero) == rightZero) {
  15.                 first ^= i; // 筛选
  16.             }
  17.         }
  18.         resArray[0] = first;
  19.         resArray[1] = eor ^ first; // eor ^ first结果就是第二个数
  20.         return resArray;
  21.     }

以上是我分享的全部内容，希望能帮助到大家

相关推荐
阅读 +

© 2020 asciim码

人生就是一场修行