异和异或

认识异或

int a = 7;
// 此时a的二进制是  0111
int b = 13;
// 此时b的二进制是  1101

那么此刻我们把 a 异或 b 会的到 10

0 1 1 1
1 1 0 1
-------
1 0 1 0

官方点来说是 相同为0 不同为1
简单来记  就是直接想加 不用进位
和同或运算进行分开

异或性质

那么由此我们可以延伸出几个性质

1. 0 ^ N = N ：0异或任何数 等于本身
2. N ^ N = 0 ：数异或本身等于0
3. a ^ b = b ^ a
4. ( a ^ b ) ^ c = a ^ ( b ^ c )
5. 同样一批数，不管是什么样的运算顺序，结果一定是一个数

异或题目

交换两个数

//通常我们以前交换两个数字是需要中间变量的
int a = 1;
int b = 2;
int c = 0;
c = a; // 1
a = b; // 2
b = c; // 1

我们学会异或以后，只需要通过三行代码就可以改变两个数，也不需要第三变量

// 为了方便记忆和理解
 a = A;
 b = B;
a = a ^ b;
b = a ^ b;
a = a ^ b;

那么此时我们来分析一下过程

1. a = a ^ b; 因为是对a的赋值操作 此刻 a = A ^ B; b = B
2. b = a ^ b; 对b的赋值操作，所以a不变；a = A ^ B; b = A ^ B ^ B; 在异或性质中我们知道，B^B=0，所以现在b = A ^ 0，一个数异或0等于本身，所以b = A;
3. a = a ^ b = A ^ B ^ A = B，此时我们完成了交换AB的算法

一个数组中出现了奇数次的数

解题思路：

​ 准备一个变量叫eor为0，让eor ^ 数组中的每个数，然后返回eor就是出现了奇数次的数

解题原理：

​ 比如我们有数组nums，值为1111222233334（为了方便提前排好序了），你拿一个eor为0去异或他们，是不是偶数的都可以消掉了，然后最后实际上你留下来的就是eor ^ 4，因为eor默认是0，所以结果也就是eor = 4

代码演示：

剑指 Offer II 070. 排序数组中只出现一次的数字

136.只出现一次的数字

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int eor = 0;
        for(int i=0; i<nums.length; i++){
            eor = eor ^ nums[i];
        }
        return eor;
    }
}

提取整形数最右侧的1

题目描述：

a = 01101110010000
ans = 0000000010000

解题思路：

a & ~a+1

a = 01101110010000

~a = 10010001101111

~a+1 = 10010001110000 +1其实是为了让在～a这一步骤变0的最右侧1再变回来

a&~a+1 = 0000000010000

a&~a+1 == a & -a ，一个数取反+1 = 这个数的相反数

数组中出现奇数次的两个数

剑指 Offer 56 - I. 数组中数字出现的次数

解题思路：

​ 首先我们还是准备一个变量eor，那么假设这个数组是nums：{1,1,2,3,4,4,5,5}，首先我们用eor^{数组中的每一位，那么出现偶数次的都可以被消除掉，最后eor=2}3，然后我们此刻 算出eor的二进制结果是

​ 2 : 0 0 1 0

​ 3 : 0 0 1 1

​ res ：0 0 0 1

​ 此时我们取最右边的1，因为这个1可以分开我们所获取的这两个数，然后此时我们有个变量叫res，首先通过上面 提取整形数最右侧的1 这个方法，把数组中所有的数字，判断一下最右边 也就是第一位 0 上是不是1，分成两组，然后有1的我们用eor去异或，自然就会得到其中出现奇数次的两个数中的一个，保存到res中，然后最后用res异或eor，就可以得到最后剩下的那个数

代码演示：

class Solution {
    public int[] singleNumbers(int[] nums) {
        int eor = 0;
        for(int i=0;i < nums.length; i++){
            eor ^= nums[i];
            //最终eor会是这两个奇数次相异或的结果
            //eor = a^b
        }
        int rightOne = eor & (~eor+1); // eor & (-eor)
        int otherOne = 0; //两个数中的其他一个
        for(int i = 0;i < nums.length; i++){
            //我们最右边那个数 是 0000001000.... 
            //如果数组中的这个数 & 最右边这个数字 不等于 0
            //就代表这个位置一定是1
            if((nums[i] & rightOne) != 0 ){
                //也就是说我的otherOne 可能是  1^2^2^4^4....(假设)
                //根据偶数相消，只会留下一个数字，就是结果之一
                otherOne ^= nums[i];
            }
        }
        //此时eor = a ^ b ，我们此刻求出a/b了
        //res 就是剩下一个
        int res = eor ^ otherOne;
        int[] ans = {res,otherOne};
        return ans;
    }
}

数组中出现K次的数

一个数组中有一种数出现了K次，其他数出现了M次，M>1，K<M，求出现K次的数

剑指 Offer 56 - II. 数组中数字出现的次数 II

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。此题目中 k为1，M为3

解题思路：

​ 我们通过一个32位的int数组来进行表示，举个例子，比如我的nums是{5,5,5,4,3,3,3}，那么我们都知道5的二进制是0101，3的二进制0011，4的二进制是0100，那么也就是说，在数组最后一位中，我们的数字类加就是6，也就是int[] nums = {00000000....000436}，也就是说6/3能整除，说明出现k次的数字最后一位不是1，3/3整除，k倒数第二位不是1，4/3有余数，那么k就在这里有1.

代码演示：

class Solution {
    public int singleNumber(int[] arr) {
        int[] t = new int[32];
        for(int num : arr){
            for(int i =0; i <= 31; i++){
                //nums >> 0就是本身 &1  其实就是与00000001
                //当 不等于0 哪一位就是1
                // if(((num >> i) & 1) !=0 ){  
                //     //如果不等于0，也就说那个位是1，所以我t[]这个位置类加1
                //     t[i]++;
                // } 
                t[i] += (num >> i) & 1;
            }
        }
        int ans = 0;
        for(int i = 0; i < 32; i++){
          //这个3 在不同题目中 可以换成M
            if(t[i] % 3 != 0){
                // 1<<移动位置到i项 
                // 然后或到ans里，就是在ans的位置上+1
                /*
                    比如ans = 00000000;
                    此刻我的t[0] != 3 也就是说我的0位是1
                    1 << 0 是000000001
                    或进取 ans = 00000001
                    1 << 1 是000000010
                    或进取 ans = 00000011
                */
                ans |= (1 << i);
            }
        }
        return ans;
    }
}

Hash表实现：

class Solution {
    public int singleNumber(int[] arr) {
       HashMap<Integer,Integer> map = new HashMap();
       //遍历一下arr
       for(int num : arr){
           //如果map中包含这个num
           if(map.containsKey(num)){
               //那么map中的num的key 就+1
            map.put(num,map.get(num)+1);
           }else{
               //否则就是map中没有这个num，就添加进去，然后num的key为1
               map.put(num,1);
           }
       }
       //把map的key都取出来遍历
      for(int num:map.keySet()){
          //如果key = 1 （也可以是k，m，n）
          if(map.get(num) == 1){
              return num;
          }
      }
      return -1;
    }
}