欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

算法之异或操作

程序员文章站 2022-04-08 18:59:58
...

异或操作
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 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. }

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