02-异或算法

2. 异或算法

2.1 异或基础

  1. 0^N == N N^N == 0;
  2. 记为无进位相加即可,1+1 = 0;
  3. 异或运算满足交换律和结合。

2.1.1 不用额外变量交换两个数

解法:aba = b,abb = a。

2.1.2 找出现奇数次的数

1. 题目

​ 一个数组中有一种数出现了奇数次,其他数都出现了偶数次,怎么找到并打印这种数。

2. 思路

​ 数组里每个元素都异或,两两相消,就只剩下奇数次的那个数

3. 代码

public static void main(String[] args) {
    int[] arr = {1,3,4,1,3,4,1,3,4,5,1,3,4};
    int ans = 0;
    for (int i = 0; i < arr.length; i++) {
        ans ^= arr[i];
    }
    System.out.println(ans);
}

2.2 提取右侧(最低位)的1

1. 题目

​ 怎么把一个int类型的数,提取出最右侧(最低位)的1来

2. 思路

1. 取反加一再和原来相与 a&(~a+1)

​ 取反:这样每一位都不一样,之前的0位置都变成了1,假设此时的值为b。

​ 加一:这样在右面+1就可以让他一直进位直到第一个0(也就是没取反的时候的1的位置),假设此时值为c。

​ 相与:此时c的状态是最低的1往右的值都是0,最低一位的1的位置和a相同,这一位再往右每一个都是不一样的,所以相与之后,直接就可以得到结果。

注意: ~a+1 就等于-a,所以也可以写成a&(-a)

2. 直接暴力

​ 先找位置,然后再把1右移

3. 代码

取反加一:

System.out.println((a&(~a+1)));
System.out.println((a&(-a)));

暴力:

private static int findRightest(int a) {
    int rightPos = 0;
    // 找最低位的1
    for(int i = 0; i < 32; i++){
        if((a & 1) == 1){
            rightPos = i;
            break;
        }
        a = a>>1;
    }

    a = 1;
    // 右移
    for (int i = 0; i < rightPos; i++) {
        a = a << 1;
    }
    System.out.println(a);
    return a;
}

2.3 找到两种奇数数

1. 题目

一个数组中有两种数出现了奇数次,其他数都出现了偶数次,怎么找到并打印这两种数

2. 思路

​ 全部异或,只留下eor = a^b

​ 因为a != b,所以二进制的ab至少有一位不一样,即eor != 0,也就是至少存在一位为1。

​ 既然有一位为1,代表a,b在这一位不同(异或:同0异1),那么就可以通过这一位来区分数组。

​ 这一位为0的放一边,为1的放一边,分别异或,这样得到的数就可以区分出来ab了。

只要是eor有一位为1就可以区分,具体是哪个无所谓,所以不妨设是最右侧的一个。

3. 代码

private static int[] getAB(int[] arr) {
    // 先异或,得到eor=a^b;
    int eor = 0;
    for (int i = 0; i < arr.length; i++) {
        eor ^= arr[i];
    }
    // 对于ab,最右侧一位的1提取出来
//        System.out.println(eor);
    int rightest = eor&(-eor);
//        System.out.println(rightest);
    // 根据这一位来区分属于谁
    // 不妨设a在这位为0,b在这位为1
    int[] ans = new int[2];
    for (int i = 0; i < arr.length; i++) {
        if((arr[i] & rightest) == 0){
            ans[0] ^= arr[i];
        }else{
            ans[1] ^= arr[i];
        }
    }
    return ans;
}

2.4 找到出现k次的数

1. 题目

​ 一个数组中有一种数出现K次,其他数都出现了M次,M > 1, K < M,

​ 要求:找到出现了K次的数,额外空间复杂度O(1),时间复杂度O(N)

2. 思路

​ 利用长度为32的数组,记录下每一位置出现1的次数,模M除K就得到二进制的所求数,再转为十进制。

3. 代码

private static int findKTimes(int[] arr, int m, int k) {
    int[] times = new int[32];
    // 记录所有数的32位的出现的次数
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < times.length; j++) {
            if((arr[i]&(1<<j)) != 0){
                times[j] ++;
            }
        }
    }
//        Arrays.stream(times).forEach(System.out::println);
    // 所有数%m/k 得到的数组合成int
    int ans = 0;
    for (int i = 0; i < times.length; i++) {
        times[i] = times[i]%m/k;
    }

    // 组合成int
    for (int i = 0; i < times.length; i++) {
        // cur = 1 1 0 1
        // times = 1 0 1 1
        ans += (times[i]<<i);
    }
    return ans;
}

热门相关:更爱熟女   黜龙   试婚老公,用点力!   法医萌妻,撩上瘾!   星界游民