算法

【体系学习003】异或及其面试题

Posted by Hilda on September 20, 2025

异或运算 (XOR) 是一种常见的二进制运算

异或运算的规则可以简单概括为：“相同为0，相异为1”。也可以理解为不进位的加法。

异或运算具有以下几个重要的数学性质，这些性质在计算机科学中应用广泛：

  1. 交换律：A⊕B=B⊕A
  2. 结合律：(A⊕B)⊕C=A⊕(B⊕C)—-可以通过“无进位相加”去理解
  3. 恒等律：任何数与 0 进行异或运算，结果仍是它本身。A⊕0=A
  4. 归零律：任何数与自身进行异或运算，结果为 0。A⊕A=0

1.如何不用额外变量交换两个数

交换步骤如下

  1. a = a ^ b
    • 此时，a 的新值包含了 a 和 b 的信息。
  2. b = a ^ b
    • 将第 1 步计算出的新 a 值（即 a ^ b）与原 b 进行异或运算。
    • 根据异或运算的性质： b=(a⊕b)⊕b=a⊕(b⊕b)=a⊕0=a
    • 此时，b 的值已经被成功替换为原来的 a 值。
  3. a = a ^ b
    • 将第 1 步计算出的新 a 值（a ^ b）与第 2 步计算出的新 b 值（也就是原 a 值）进行异或运算。
    • 根据异或运算的性质： a=(a⊕b)⊕a=(a⊕a)⊕b=0⊕b=b
    • 此时，a 的值已被成功替换为原来的 b 值。

【注意】：交换数组中两个位置的数，可以这么写，但是有前提条件\(i \ne j\):

1
2
3
4
5

public static void swap(int[] arr, int i, int j) {
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}

如果\(i = j\)，那么arr[i] ^ arr[j]的结果就是0，那么第二行，就会得到arr[j] = 0 ^ arr[j];，则arr[j] 就是arr[j] ，紧接着第三行就是arr[i] = 0 ^ arr[j]，arr[i]也会变成arr[j]。

即如果\(i=j\)无论 arr[i] 原本是什么值，经过这三步异或运算后，arr[i] 的值最终都会变为 0。这并非是简单地保持不变或者变成另一个数，而是会丢失原始数据。因为i等于j，所以指向同一块内存区域，都变成了0.

因此，这个异或交换法必须满足\(i\ne j\)这个前提条件，否则会发生错误。

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

常规方法：哈希表

但是用异或运算可以使得空间复杂度更好。

试题链接：https://www.nowcoder.com/practice/d0ef3e33e63a49dd99c90aeef306b0fc

解法：（这题是ACM风格）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

import java.util.Scanner; 
import java.io.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            int n = (int)in.nval;
            in.nextToken();
            int[] arr = new int[n];
            for (int i = 0;i < n;i++) {
                arr[i] = (int)in.nval;
                in.nextToken();
            }
            int ans = findOddNum(arr);
            out.println(ans);
        }
        out.flush();
        br.close();
        out.close();
    }

    public static int findOddNum(int[] arr) {
        int ans = 0;
        for (int i = 0;i < arr.length;i++) {
            ans ^= arr[i];
        }
        return ans;
    }
}

3.怎么把一个int类型的数提取出最右侧的1来

方法是:N&(-N)，就是&上自己的相反数

N & (~N + 1) 就能高效地提取出 N 二进制表示中最右边的“1”。这种方法通常用于快速计算一个数中“1”的个数，或者在树状数组中进行索引操作。

这么做的原因是：~N + 1 的二进制表示中，最右边的“1”会和 N 中最右边的“1”处于同一个位置。而且，它左边的所有位都与 N 相反。所以

N & (~N + 1)：

  • 在最右边的“1”的左边，N 和 ~N + 1 的位是相反的，所以按位与的结果都是“0”。
  • 在最右边的“1”这个位置上，N 和 ~N + 1 都是“1”，所以按位与的结果是“1”。
  • 在最右边的“1”的右边，N 和 ~N + 1 都是“0”，所以按位与的结果都是“0”。

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

题目链接：https://www.nowcoder.com/questionTerminal/863d84dc0b2d4e639dc17f12701ed3ac

(上面这个测试链接是ACM风格的)

另外这道题被包装成了力扣的一道题LCR 177. 撞色搭配

这种题目更加具有扩展性的问法是：

一个数组中有一种数出现K次，其他数都出现了M次， 已知M > 1，K < M，找到出现了K次的数 要求额外空间复杂度O(1)，时间复杂度O(N)

显然题目要求已经将哈希表的解法给否定了。

先看2个数出现奇数次的情况。

首先如果还是将所有数进行异或，最终得到的结果就是ans=a^b，因为\(a \ne b\)所以\(ans \ne 0\)。

即ans的二进制表示中，一定有一个位置上是1.

利用上面的解法，找到ans中最右侧的1.那么说明a与b这个位置上的数一定是不同的，一定某个数这个位置是0，某个数这个位置是1.（下面的讨论假设ans的1出现在第i位置上，假设a的i位置上是1，b的i位置上是0）。

现在整个数组可以分为2个阵营，如下图所示：

image-20250920174459078

现在变量eor仍旧去异或数组中的数，但是只异或i位置是1的数。这样就会得到eor = a，

如何得到b呢？就是ans ^ eor

所以上面测试链接的解法是：（注意这题是ACM风格的）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

import java.util.Scanner;
import java.io.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args)  throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            int n = (int)in.nval;
            in.nextToken();
            int[] arr = new int[n];
            for (int i = 0;i < n;i++) {
                arr[i] = (int)in.nval;
                in.nextToken();
            }
            int[] ans = getNums(arr, n);
            int small = ans[0] < ans[1] ? ans[0] : ans[1];
            int big = ans[0] == small ? ans[1] : ans[0];
            out.print(small + " ");
            out.print(big);
        }
        out.flush();
        br.close();
        out.close();
    }

    public static int[] getNums(int[] arr, int n) {
        int ans = 0;
        for (int i = 0;i < n;i++) {
            ans ^= arr[i];
        }
        // ans = a ^ b
        // 找到最右侧的1
        int rightOne = ans & (~ans + 1);
        int eor = 0;
        for (int i = 0;i < n;i++) {
            if ((arr[i] & rightOne) != 0) {
                eor ^= arr[i];
            }
        }
        // a = eor
        // b = ans ^ eor
        return new int[] {eor, ans ^ eor};
    }
}

5.一个数组中有一种数出现K次，其他数都出现了M次

一个数组中有一种数出现K次，其他数都出现了M次， 已知M > 1，K < M，找到出现了K次的数 要求额外空间复杂度O(1)，时间复杂度O(N)

准备一个int[] t = new int[32]，任何一个数（int类型）都可以表示成32位的二进制，那么对于一个数组nums，可以算每一个数每一位上1出现的个数，存储在数组t中。

只需要判断t中每个元素是否被M整除，就可以判断出现K次的数这个位置是不是1

能被M整除，那么出现K次的数这个位置不是1；不能被M整除，出现K次的数这个位置是1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public static int onlyKTimes(int[] arr,int k,int m){
  int[] t=new int[32];
  for(int num:arr){
    for(int i=0; i<=31; i++){
      t[i]+=(num>>i)&1;
    }
  }
  int ans=0;
  for(int i=0; i<32; i++){
    if((t[i]%m)!=0){// 在第i位上有1
      ans |= (1<<i);// 1左移i个位置
    }
  }
  return ans;
}

相关题可以看下面的例子。

k=1,m=3的例子就是力扣137题

6.力扣136

https://leetcode.cn/problems/single-number/

1
2
3
4
5
6
7
8
9

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

7.力扣137

https://leetcode.cn/problems/single-number-ii/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int singleNumber(int[] nums) {
        return getKtimesBetweenM(nums, 1, 3);
    }
    public int getKtimesBetweenM(int[] arr, int k, int m) {
        int[] t = new int[32];
        for (int i : arr) {
            for (int j = 0;j <= 31;j++) {
                t[j] += ((i>>j)& 1);
            }
        }
        int ans = 0;
        for (int i = 0;i <= 31;i++) {
            if (t[i] % m != 0) {
                ans |= (1 << i);
            }
        }
        return ans;
    }
}

8.LCR 177. 撞色搭配

LCR 177. 撞色搭配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int[] sockCollocation(int[] sockets) {
        int ans = 0;
        for (int i : sockets) {
            ans ^= i;
        }
        // ans = a ^ b
        // 找到某个1，比如最右侧1
        int rightOne = ans & (~ans + 1);
        int eor = 0;
        for (int i : sockets) {
            if ((i & rightOne) != 0) {
                eor ^= i;
            }
        }
        // eor = a;
        return new int[] {eor, eor ^ ans};
    }
}

9.力扣260. 只出现一次的数字 III

260. 只出现一次的数字 III

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
    public int[] singleNumber(int[] nums) {
        int ans = 0;
        for (int i : nums) {
            ans ^= i;
        }
        // ans = a ^ b
        int rightOne = ans & (~ans + 1);
        int eor = 0;
        for (int i : nums) {
            if ((i & rightOne) != 0) {
                eor ^= i;
            }
        }
        // eor = a
        return new int[] {eor, eor ^ ans};
    }
}

10.LCR 004. 只出现一次的数字 II

LCR 004. 只出现一次的数字 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public int singleNumber(int[] nums) {
        return getKtimesBetweenM(nums, 1, 3);
    }

    public int getKtimesBetweenM(int[] arr, int k, int M) {
        int[] t = new int[32];
        for (int i : arr) {
            for (int j = 0;j <= 31;j++) {
                t[j] += ((i>>j) & 1);
            }
        }
        int ans = 0;
        for (int i=0;i <= 31;i++) {
            if (t[i] % M != 0) {
                ans |= (1 << i);
            }
            
        }
        return ans;
    }
}

11.牛客类似题目

https://www.nowcoder.com/practice/c04bd25f0396471b90dfc30d96b9109b?fromPut=????pc????_???????_2008263481696810321082

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int singleNumber (int[] nums) {
       int ans = 0;
       for (int i : nums) {
            ans ^= i;
       }
       return ans;
    }
}

https://www.nowcoder.com/practice/389fc1c3d3be4479a154f63f495abff8?tpId=13

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型一维数组
     */
    public int[] FindNumsAppearOnce (int[] nums) {
        int ans = 0;
        for (int i : nums) {
            ans ^= i;
        }
        // ans = a ^ b
        int rightOne = ans & (~ans + 1);
        int eor = 0;
        for (int i : nums) {
            if ((i & rightOne) != 0) {
                eor ^= i;
            }
        }
        // eor = a
        int b = eor ^ ans;
        if (b < eor) return new int[] {b, eor};
        
        return new int[]{eor, b};
    }
}

https://www.nowcoder.com/practice/85cb47fc0c6c483fab7e5cefab54d9e5?tpId=365&tqId=2313031&ru=/exam/oj&qru=/ta/spring-deliver-2024/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D365

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型
     */
    public int singleNumber (int[] nums) {
        return getKFromM(nums, 1, 3);
    }
    public int getKFromM(int[] arr, int k, int m) {
        int[] t = new int[32];
        for (int n : arr) {
            for (int i = 0;i <= 31;i++) {
                t[i] += ((n >> i) & 1);
            }
        }

        int ans = 0;
        for (int i = 0;i <= 31;i++) {
            if (t[i] % m != 0) {
                ans |= (1 << i);
            }
        }
        return ans;
    }
}

https://www.nowcoder.com/practice/1097ca585245418ea2efd0e8b4d9eb7a

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

import java.util.*;


public class Solution {
    /**
     * 
     * @param A int整型一维数组 
     * @return int整型
     */
    public int singleNumber (int[] A) {
        return getKfromM(A, 1, 3);
    }

    public int getKfromM(int[] arr, int k, int M) {
        int[] t = new int[32];
        for (int n : arr) {
            for (int i = 0;i <= 31;i++) {
                t[i] += ((n >> i) & 1);
            }
        }
        int ans = 0;
        for (int i = 0;i <= 31;i++) {
            if (t[i] % M != 0) {
                ans |= (1 << i);
            }
        }
        return ans;
    }

}
CATALOG
    FEATURED TAGS
    书籍阅读 算法 人工智能AI基础 python基础 力扣 numpy pandas 机器学习-吴恩达 机器学习算法 matplotlib spring6 算法题库 Java基础 java集合 ollama工具 python爬虫
    FRIENDS