算法-面試題系列-異或運算

認(rèn)識異或運算

• 異或運算:相同為0,不同為1
• 同或運算:相同為1，不同為0

能長時間記住的概率接近0%

所以，異或運算就記成無進(jìn)位相加!

題目一

• 如何不用額外變量交換兩個數(shù)

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

題目二

• 一個數(shù)組中有一種數(shù)出現(xiàn)了奇數(shù)次，其他數(shù)都出現(xiàn)了偶數(shù)次，怎么找到并打印這種數(shù)

image-20210515214126342

最后xor等于多少，奇數(shù)次出現(xiàn)的數(shù)就是這個數(shù)。 因為偶數(shù)次的數(shù)異或后的值為0 即a^a = 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);
}

題目三

• 怎么把一 個int類型的數(shù)，提取出最右側(cè)的1來

N & (~N+1)

image-20210515215228449

image-20210515215506340

題目四

• 一個數(shù)組中有兩種數(shù)出現(xiàn)了奇數(shù)次，其他數(shù)都出現(xiàn)了偶數(shù)次，怎么找到并打印這兩種數(shù)！

第一步 把數(shù)組中所有的數(shù) xor(異或) 得到一個結(jié)果 eor 則記過肯定是是奇數(shù) a 與 奇數(shù) b 異或的結(jié)果！因為偶數(shù)次的數(shù)異或完之后為0

第二步 找到 eor 上最后側(cè)的1出來 ， 假設(shè)為第N位 ， 則奇數(shù)次 a 與 奇數(shù)次 b 的第N位==一定不一樣== 否則這一位不可能為1

image-20210515220558959

因為 奇數(shù)次 a 與 奇數(shù)次 b 的第N位==一定不一樣== ，所以a b 一定不能被分在同一個部分里面

把第N為1的部分全部異或一遍得到eor2 得到的eor2就是奇數(shù)次 a 與 奇數(shù)次 b中的其中一個數(shù)

// arr中，有兩種數(shù)，出現(xiàn)奇數(shù)次
public static void printOddTimesNum2(int[] arr) {
   int eor = 0;
   for (int i = 0; i < arr.length; i++) {
      eor ^= arr[i];
   }
   // a 和 b是兩種數(shù)
   // eor != 0
   // eor最右側(cè)的1，提取出來
   int rightOne = eor & ((~eor)+1); // 提取出最右的1
   
   
   int onlyOne = 0; // eor'
   for (int i = 0 ; i < arr.length;i++) {
      //  arr[1] =  111100011110000
      // rightOne=  000000000010000
      if ((arr[i] & rightOne) != 0) {//分組中第N為1的部分異或
         onlyOne ^= arr[i];
      }
   }
   System.out.println(onlyOne + " " + (eor ^ onlyOne));
}