codeforces-go 题解：LeetCode 双周赛 121 的「使数组异或结果等于 K」——异或性质 + popcount 的位运算思维

本篇技术指南围绕 codeforces-go 仓库中收录的 LeetCode 双周赛 121 第 2 题（使数组异或结果等于 K 的最少操作次数）展开，系统拆解该题背后的异或（XOR）性质推导、比特位翻转的最优性证明，以及 Python / Java / C++ / Go 四种语言的标准解法，并结合仓库内的 Go 实现与测试框架，说明如何在本地用官方程式模板验证该题解。读完本篇后，你将掌握一类「异或目标等价转化 + 二进制 1 的个数」的位运算题型的完整解题范式。

一、题目与核心结论

题目要求：给定整数数组 nums 和一个整数 k，每一步操作可以翻转 nums 中任意一个数字的任意一个比特位，问最少需要多少次操作，才能让整个数组的异或和等于 k。

记 nums 全体元素的异或和为 s，即：

s = nums[0] ^ nums[1] ^ ... ^ nums[n-1]

题解文档给出了三个关键推导（见 README.md）：

1. 目标等价转化：s = k 等价于 s ^ k = 0。也就是说，问题从「把异或和变成 k」等价转化为「把某个目标值 x 变成 0」，其中 x = s ^ k。
2. 翻转与异或的联动：x = s ^ k 恰好是「原数组异或和」与「目标值」的异或差。若把 nums 中任意一个数字的某个比特位翻转，那么 s（进而 x）的同一个比特位也会翻转——因为异或结果中某一位的值只由参与异或的各数在该位上的取值决定，翻转其中一个数在该位的值，结果位必然翻转。
3. 最少操作数：要让 x 变为 0，必须把 x 中每一个为 1 的比特位都翻转一遍；而翻转某一位只需一次操作。因此最少操作次数就是 x = s ^ k 中二进制 1 的个数，即 popcount(s ^ k)。

这一步推导的巧妙之处在于：我们不需要真的去考虑翻转「哪个数」的「哪一位」——由于每一位之间相互独立，翻哪些数只是「谁去承担这次翻转」的问题，而操作次数只取决于必须翻转的位的数量，与选择哪个数无关，因此答案具有唯一性且必然最优。

二、四种语言的标准实现

以下代码均来自题解文档（见 README.md），每段都严格实现了 popcount(异或和 ^ k) 这一结论。

Python3

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        return (reduce(xor, nums) ^ k).bit_count()

Java

class Solution {
    public int minOperations(int[] nums, int k) {
        for (int x : nums) {
            k ^= x;
        }
        return Integer.bitCount(k);
    }
}

C++

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        int sum = reduce(nums.begin(), nums.end(), k, bit_xor());
        return popcount((uint32_t) sum);
    }
};

Go

func minOperations(nums []int, k int) int {
	for _, x := range nums {
		k ^= x
	}
	return bits.OnesCount(uint(k))
}

四个版本的本质完全相同：先让 k 与每个 nums[i] 异或（相当于计算 s ^ k），再统计结果中 1 的个数。语言层面的差异只在于「统计二进制 1 个数」的 API：Python 用 int.bit_count()，Java 用 Integer.bitCount()，C++ 用 popcount()，Go 用 math/bits 包中的 bits.OnesCount()。

复杂度分析（与原文档一致）：

• 时间复杂度：O(n)，其中 n 为 nums 的长度。只需一趟遍历完成异或，随后 popcount 在定长机器字内完成，视为常数时间。
• 空间复杂度：O(1)。全程只使用常数个变量，不依赖 n 的额外空间。

三、仓库内的 Go 实现：源码级印证

题解文档对应的代码，在仓库中以竞赛题单的形式落地为可编译、可测试的 Go 程序，位于 leetcode/biweekly/121/b/。

核心实现 b.go：

package main

import "math/bits"

// https://space.bilibili.com/206214
func minOperations(nums []int, k int) int {
	for _, x := range nums {
		k ^= x
	}
	return bits.OnesCount(uint(k))
}

值得注意两个实现细节：

• 复用入参 k 作为累加异或的载体，省去单独的 s 变量，与 README 中 Java 版本的写法一致；
• 返回前将 k 转换为 uint 再调用 bits.OnesCount，这是因为 OnesCount 接收无符号整数；int 与 uint 的位模式一致，转换不改变二进制 1 的个数，仅满足 API 签名要求。

测试驱动 b_test.go：

func Test_b(t *testing.T) {
	if err := testutil.RunLeetCodeFuncWithFile(t, minOperations, "b.txt", 0); err != nil {
		t.Fatal(err)
	}
}

该测试通过 testutil.RunLeetCodeFuncWithFile 从同目录的 b.txt 读取用例：文件每 入参个数 + 出参个数 行组成一组测试数据，函数内部利用反射把文本解析为函数入参、调用被测函数，并把实际输出与期望输出比对。也就是说，仓库内的题目验证遵循「源码 + 测试数据文件 + 反射式测试驱动」的统一范式，你可以直接在该目录下运行 go test 复现题解的正确性。

测试用例 b.txt 中共两组数据：

[2,1,3,4]
1
2

[2,0,2,0]
0
0

逐一验证推导结论：

• 用例 1：nums = [2,1,3,4]，异或和 s = 2^1^3^4 = 4，s ^ k = 4 ^ 1 = 5，二进制为 101，1 的个数为 2，输出 2 ✓
• 用例 2：nums = [2,0,2,0]，异或和 s = 2^0^2^0 = 0，s ^ k = 0 ^ 0 = 0，1 的个数为 0，输出 0 ✓

两组用例恰好覆盖了「答案非零」与「答案为零（数组异或和已等于 k，无需任何操作）」两种情形。

四、从题目到模板：popcount 与位运算知识沉淀

这道题的核心工具 popcount（二进制 1 的个数）在 codeforces-go 仓库的 copypasta/bits.go 中有成体系的笔记沉淀，可以看作该题解在算法模板库层面的延伸，例如：

• OnesCount 相当于二进制的 digsum（数字位和），其数列对应 OEIS A000120；
• popcount(x XOR y) % 2 = (popcount(x) + popcount(y)) % 2，即异或结果的奇偶性可由两数 popcount 的奇偶性推得（Codeforces 1615D 曾用此结论）；
• popcount(a&b) + popcount(a|b) = popcount(a) + popcount(b) 这类恒等式可用于区间、子集类问题；
• 特别地，y 的最右边的比特就是 bits.OnesCount(x) % 2，这类逐位性质常与异或、构造题结合。

从本题的推导可以看出这类题型的通用解题路径：先用异或恒等式把「目标」转化为「差值」（s ^ k），再抓住「翻转某一位只影响结果中对应一位」的独立性，把问题归结为统计二进制 1 的个数。这也是「位运算」题单中「恒等式 + 思维」类题目的典型代表（仓库 README 中将其归入位运算分类题单）。当你遇到「最少修改多少个比特/元素才能使整体满足某异或条件」的题目时，可以优先尝试这条思路。

五、小结

「使数组异或结果等于 K」是一道极具代表性的位运算思维题：答案不是靠模拟翻转过程得到的，而是靠三条异或性质一步推导出来——s = k ⟺ s ^ k = 0、翻转某一比特只联动结果对应位、x 中每个 1 都必须且只能被翻转一次，因此答案即 popcount(s ^ k)。四种语言的实现彼此印证，而仓库中的 b.go、b_test.go 与 b.txt 三件套又给出了可直接编译运行的完整证据链；配合 copypasta/bits.go 中的 popcount 性质笔记，你可以把本题的解法推广到更广泛的异或与位运算问题中。