前几天做每日一题正好碰到 LeetCode 3226「使两个整数相等的位更改次数」。题目很短评级也标着 easy但如果你对“位运算、整数”的基础掌握得不够牢第一次提交很容易踩坑。我当时就错了一次原因是题目里藏了一个关键约束每次操作只能把某个二进制位上的 1 改成 0不能反向把 0 改成 1。这个限制一旦没看清你会直接往“汉明距离”方向写而那个答案在本题里只有一部分成立。这道题非常适合用来串一遍位运算的基础按位与、按位异或、统计 1 的个数、以及如何判断一个整数的位集合是否包含另一个整数。这篇文章我会从题意拆解开始讲清楚为什么“只能把 1 改成 0”改变了整个解题方向再给出逐位扫描和一行公式两种实现最后聊聊我在提交和测试中碰到的边界问题以及这类题背后通用的二进制集合模型。无论是刚开始刷题的初学者还是想快速回顾位运算技巧的老手都可以从里面拿走点东西。1. 题意里的隐藏约束不是随便改而是只能“删 1”1.1 从一个最容易错的示例看起先看一个具体的例子。假设n 13k 4问最少需要几次位更改才能让n变成k。把两个整数展开成二进制13 11014 0100如果把“位更改”理解成可以任意把 0 改成 1、把 1 改成 0那么只需要看两个数有多少位不一样1101和0100在第 3 位、第 0 位不一致汉明距离是 2所以答案就是 2。但题目里真正的规则是每次只能把一个 1 改成 0。这意味着二进制位上的变化只能朝一个方向走所有原本是 0 的位都不能变成 1。13的第 0 位是 14的第 0 位是 0这个 1 可以删掉第 3 位同样是 1 变 0也可以删掉但是第 1 位13是 04也是 0没有变化需求。所以答案确实是 2。表面上看这个例子和汉明距离算出来的结果一样可只要换一个例子就会露馅。比如n 2k 12 101 01从 0 变成 1 是不允许的所以n永远无法变成k应该返回-1。而如果直接算2 ^ 1 3二进制是11popcount 为 2就会错误地认为答案是 2。这也说明解的公式必须在“只允许 1 变 0”这个前提下推导不能看见“位更改次数”就套汉明距离。1.2 把二进制理解为“1 的集合”要摆脱这种混淆最好的办法是把整数看成一个集合集合里的元素就是二进制位中被置 1 的那些位置。比如n 13对应二进制1101第 3 位、第 2 位、第 0 位是 1它的“1 的集合”就是{3, 2, 0}。k 4对应0100集合是{2}。题目要求的“只能把 1 改成 0”翻译成集合语言就非常清楚你只能从n的集合中删除元素不能添加元素。目标集合是k的集合那么如果k的集合里有某个元素但n的集合里根本没有那么无论怎么删都凑不出k结果无解。如果k的集合是n的集合的子集那么答案就是n的集合大小减去k的集合大小因为需要把多出来的那些 1 全部删掉。这个“子集”视角是整道题的灵魂。后面所有代码里的(n k) k本质上就是在判断k的每个 1 是不是都已经被n包含了。1.3 什么时候必然无解什么时候返回-1可以归纳成一个非常简单的条件n的二进制中某一位是 0而k的同一位是 1。因为 0 没办法变成 1。举个例子n 5k 3。5 1013 011n的第 0 位是 0k的第 0 位是 1这就是一个无法满足的“新增 1”请求。不管删掉n里的哪个 1第 0 位始终是 0所以无解。用位运算来判断这个条件比逐位检查更简洁先做n k它会把n和k同时为 1 的位保留下来。如果n k等于k说明k里的每一个 1 都在n里有对应如果不等于说明k至少有一个 1 是n没有的。我第一次做题时没有意识到这个判断靠直觉先写了return (n ^ k).bit_count()结果在n 2, k 1这种用例上直接挂掉。后来把题意翻译成集合才发现“无解”的判断根本绕不开这也是这道题和普通“最小位翻转次数”最大的区别。2. 看懂三个位运算这题就解了一半2.1 按位与 n k判断 k 的 1 是否都在 n 里按位与的规则很直白两个二进制位都是 1结果才是 1。这正好对应“集合交集”的概念。对于本题n k的结果表示同时存在于n和k里的 1。如果k是n在 1 的位置上的子集那么n k应该把k的每一个 1 都保留下来结果恰好等于k。用代码写就是if ((n k) ! k) { return -1; }这一行相当于在做快速判断把所有“k 里有 1、n 里没有 1”的无解情况挡在门外。注意这里不能用去比较大小关系因为二进制位是否包含跟数值大小没有直接关系。比如n 6110k 4100k的数值更小但k是n的位集合子集条件是成立的而n 6k 5101虽然k也小于n但n没有第 0 位的 1条件不成立。所以必须逐位判断。如果你接触过状态压缩动态规划对这个模式一定不陌生。判断一个状态是否包含某个子状态经常写作(mask need) need。这里的mask就是nneed就是k题目直接把这个子集判断变成了主菜。2.2 按位异或 n ^ k两数哪些位不同按位异或的规则是两个二进制位不同结果为 1相同结果为 0。所以n ^ k的二进制结果里所有为 1 的位恰好就是“两个数不一致的位”。在“只允许 1 变 0”的约束下一旦(n k) k成立n和k不一致的地方就不可能出现“k是 1、n是 0”的情况只会是“n是 1、k是 0”。也就是说差异位的集合恰好就是需要从n中删除的 1 的集合。举个例子n 13二进制1101k 4二进制0100n ^ k 9二进制10011001里有两个 1分别对应第 3 位和第 0 位这两处正是需要把 1 改成 0 的位置。因此答案可以直接等于(n ^ k)这个数中 1 的个数。如果题目允许双向修改答案也是(n ^ k)的 1 个数但区别在哪区别在没有无解判断。双向修改时任何两个整数都能通过翻转差异位互相转换不存在-1单向修改时必须先满足(n k) k否则异或结果里那些 1 可能代表“需要把 0 变成 1”这是不允许的答案也就不是简单的 popcount。2.3 统计 1 的三种写法既然知道了n ^ k之后要统计 1 的个数那就要掌握至少三种写法不同语言和场景下总有一款适合你。第一种是语言自带的方法。Python 里整数对象直接带bit_count()C 里可以用__builtin_popcountJava 里是Integer.bitCount。这三者在竞赛和 LeetCode 场景下都足够快而且可读性最好return (n ^ k).bit_count()return __builtin_popcount(n ^ k);return Integer.bitCount(n ^ k);第二种是逐位判断适合在没有内置函数的语言里自己实现。思路是不断看最低位是不是 1然后右移一位int countOne(int x) { int cnt 0; while (x) { cnt (x 1); x 1; } return cnt; }第三种是 Brian Kernighan 算法利用x (x - 1)每次消掉二进制中最右边的 1。循环次数只等于二进制中 1 的个数比逐位遍历更省int countOne(int x) { int cnt 0; while (x) { x (x - 1); cnt; } return cnt; }第三种方法是我个人最喜欢用来手写 popcount 的方式。它不需要遍历所有位只处理有 1 的位置在整数位宽较大但 1 很少时效率特别高。理解它也有助于加深对“减 1 会改变最低位 1 及其右侧所有位”这一位运算规律的认识。3. 从逐位检查推出 O(1) 公式解3.1 最符合直觉的逐位扫描实现先不要急着写一行公式我们从一个最保守、最不容易出错的实现开始一位一位地检查n和k的二进制。逐位扫描的核心逻辑是如果k当前位是 1n当前位是 0说明需要一个“0 变 1”的操作返回-1。如果n当前位是 1k当前位是 0说明这个 1 需要被删除计数加一。然后两个数同时右移一位继续检查下一位。写成 Python 是这样class Solution: def minChanges(self, n: int, k: int) - int: ans 0 while n or k: if (k 1) and not (n 1): return -1 if (n 1) and not (k 1): ans 1 n 1 k 1 return ans为什么循环条件是while n or k因为当n变成 0 时k可能还残留着 1这时候还要继续检查这些位置是否会造成无解。比如n 1k 2第一次迭代时检查最低位n有 1k没有 1计数加一n变成 0k变成 1第二次迭代发现k有 1、n没有 1于是返回-1。这一步是必须的不能只写成while n。逐位扫描的好处是逻辑直观每一处判断都能和题意的“1 变 0”一一对应适合用来验证自己对题目的理解。缺点是代码啰嗦而且如果两个数很大需要遍历的位数增加。不过因为数值范围通常不超过 32 位性能差别并不明显。3.2 用位运算压缩判断一行核心逻辑当你已经理解了子集判断就可以把逐位扫描压缩成三个步骤(n k) ! k则返回-1。计算diff n ^ k。返回diff的 1 的个数。合起来就是开头展示的那种写法class Solution: def minChanges(self, n: int, k: int) - int: if (n k) ! k: return -1 return (n ^ k).bit_count()C 版本一样清爽class Solution { public: int minChanges(int n, int k) { if ((n k) ! k) return -1; return __builtin_popcount(n ^ k); } };这里要注意__builtin_popcount在 GCC 系列编译器里接受的是unsigned int类型。题目给的n、k都是正整数一般不会出现符号位问题但如果你的环境里把整数扩展到了 64 位建议使用__builtin_popcountll避免高位丢失。Java 则直接用Integer.bitCount就没这么多烦恼。这版代码看着短但它不是“背下来就行”的代码而是前两节所有概念的浓缩。你在写这行代码之前必须能在脑子里完成这样的推导现在n的 1 集合比k多多的部分用n ^ k表示只允许删 1 所以删掉这些多出来的 1 即可。只要推导过程清楚代码抄不抄都无所谓。3.3 证明为什么 (n ^ k).bit_count() 就是答案可能有朋友会问既然(n k) ! k才返回-1那在条件成立的情况下直接用popcount(n) - popcount(k)是不是也可以答案是也可以因为两个答案在这种情况下相等。我们把二进制位分成三类来证明第一类n 1k 1。这类位在n ^ k中为 0对最终答案没有贡献。第二类n 1k 0。这类位在n ^ k中为 1是唯一需要执行“1 变 0”的位置每出现一次答案加 1。第三类n 0k 1。如果存在这类位置直接无解。而(n k) k这个条件恰好排除了这种情况。所以在条件成立时n ^ k中 1 的个数等于第二类位置的数量也就是真正需要更改的次数。由于第二类位在n中都是 1、在k中都是 0它同时也等于n的 1 的数量减去k的 1 的数量。这个证明过程比结论本身更重要。它解释了为什么不能只背公式而是要在每一步都问一句当前这个差值位是否真的对应一个允许执行的操作位运算题目最常见的陷阱就是“运算结果看着对但操作语义对不上”。4. 提交过程中踩过的边界和性能问题4.1 n k 与 k 更大的边界先看最简单的边界如果n k不需要任何更改答案应该是 0。套到公式里(n k) ! k不成立因为n k n k然后n ^ k 0bit_count()返回 0。所以不需要特判公式自动覆盖。相比之下逐位扫描版本同样不需要特判因为两个数相同意味着没有任何一位触发计数或返回-1的条件。另一种情况是k比n更大。比如n 2k 3n 10k 11k的最低 1 位是n没有的因此无解。这会让很多不熟悉位运算的人困惑明明 3 比 2 大为什么反而返回-1其实数值大小和二进制位的子集关系没有必然联系。k比n大只说明整体数值更高但有没有“新增的 1 位”才是关键。比如n 81000k 70111n的数值比k大但仍然无解因为k拥有三个n没有的低位 1。4.2 位宽和 32 位有符号整数的迷惑LeetCode 给的n、k一般都在 32 位有符号整数范围内也就是1 n, k 2^31所以最高位都是 0。但这不代表你可以忽视位宽问题。C 里如果直接在int上做__builtin_popcountwhile 循环或者内置函数都不会出错因为正数的右移是逻辑右移还是算术右移不会影响最终结果。但如果你把变量声明成负数比如把某个计算结果误存成int并且最高位是 1那么__builtin_popcount的行为可能会因为参数隐式转换而和你预期不一致。稳妥的做法是用unsigned int来承载位运算结果。Python 不存在这个问题因为它的整数是任意精度的。你甚至可以把n和k设成10^18也不会溢出bit_count()依然能正确统计。这一点在做大数位运算时非常舒服但也会掩盖一个问题在 C 里如果题目数值超过int范围必须改用long long同时把__builtin_popcount换成__builtin_popcountll否则统计结果会丢位。我实际测试过一组数据n 2_000_000_000k 1_000_000_000这在int范围内。但如果把n设成接近2^31 - 1再配合某些需要翻转的测试点手动逐位while (n || k)仍然安全因为右移正数时高位补 0。真正的坑往往出现在把结果算成负数的那一瞬间而不是循环本身。4.3 内置 bit_count 与手写循环的实际表现很多初学者担心bit_count()是不是不够快其实完全没必要。在 LeetCode 这种单个测试用例规模下内置调用是经过底层指令优化的比手工逐位循环快不少。我自己在本地对1e7个随机整数做 popcount 测试时Python 的int.bit_count()大概是手写while x循环的 5 到 8 倍。原因是它直接用 CPU 级别的位计数指令完成而 Python 循环每处理一位都要做解释器操作。C 的__builtin_popcount在支持 POPCNT 指令集的机器上也会被编译成一条指令性能更不用多说。所以在能使用内置方法的语言里优先使用内置方法没有必要为了“看起来更底层”而手写。但如果你所在的场景不支持内置函数比如某些嵌入式环境或者需要自己实现一个基础库建议选择 Brian Kernighan 算法而不是逐位扫描。因为工程实践中很多整数的二进制位都比较稀疏x (x - 1)的循环次数只等于 1 的个数平均性能更好。我在这里也踩过一个不大不小的坑早期写 C 代码时我用for (int i 0; i 32; i)逐位遍历然后判断(x i) 1。这个方法没问题但在某些编译器优化级别下x i会被重新计算多次导致代码膨胀。改成while (x) { cnt x 1; x 1; }之后不仅代码更短性能也更稳定。对于本题这种只需要统计一次差异位的场景这些区别可以忽略但作为习惯我建议把“循环右移”和“Kernighan 消 1”两种写法都记住。5. 从一个题到一类题位集合包含模型5.1 本质抽象用集合删除模拟位变化如果你把这道题做完就翻篇有点可惜。它背后是一个适用范围很广的模型把二进制位看作集合元素把位操作看成集合操作。在这个模型里n k是交集。n | k是并集。n ^ k是对称差。(n k) k是子集判断。n的 popcount 是集合大小。本题限制“只能把 1 改成 0”就是在说只能对集合做删除不能做添加。于是问题变成“能否通过删除元素把集合 A 变成集合 B”答案要么是“无条件”要么是“集合大小差”。这个抽象能帮你很快判断一道新题能不能用位运算做。只要题目中出现“两个整数”“二进制位”“只能翻转某个方向”“判断子集”“统计不同位的数量”都可以先往位集合模型上靠。比如要判断一个数是否包含在另一个数里直接(a b) b要求两个数的公共保留位直接a b要求两个数合并后有哪些位直接a | b。5.2 同类型的变形题一览LeetCode 里和这道题相关的题目不少我把它们放在一起对比一下方便建立知识网络题目核心操作与本题的关系191. 位 1 的个数统计 popcount本题重叠知识点461. 汉明距离任意位翻转求差异位数量本题如果允许双向修改答案就是汉明距离2220. 转换数字的最少位翻转次数可以 0 变 1也可以 1 变 0使用popcount(start ^ goal)没有无解判断3226. 使两个整数相等的位更改次数只能 1 变 0需要判断(n k) k再用popcount(n ^ k)看到第 2220 题你会更清楚为什么 3226 值得单独拿出来讲。同样都是算“翻转几次才能相等”2220 允许双向翻转任何一对整数都有答案3226 限制为单向于是无解判断成了核心。两道题放在一起刷能直观感受到“约束条件如何改变公式形态”。还有一个常见的变体是反向限制“只能把 0 改成 1不能把 1 改成 0”。这种题把集合包含方向反过来无解判断从k ⊆ n变成n ⊆ k判断条件写成(n k) n答案依然是popcount(n ^ k)。理解了位集合模型这些变体都不用重新学改一行条件就行。5.3 状态压缩里的一个意外收获除了刷题这个模型在状态压缩动态规划里也特别常见。比如有一个mask表示已经选择的元素集合某个子任务要求必须已经选择了need这些元素才能执行那么判断条件可以直接写if ((mask need) need) { // 可以执行 }这和本题判断k是否包含在n里是同一个模式。我在写旅行商问题、子集枚举、状压 DP 的依赖关系时经常用到这个表达式。它让代码从“遍历逐个元素检查”变成 O(1) 的位运算而且不容易写错。另一个常用技巧是枚举子集for (int sub mask; sub; sub (sub - 1) mask) { // 处理子集 sub }这段代码每次生成mask的一个真子集本质上也是在操作“位集合删除元素”。如果你理解了 3226 的“删 1”思想再回头看这个枚举子集循环就会知道它为什么用(sub - 1) mask减一会把最低位的 1 变成 0再与mask做按位与就只会在mask的 1 位范围内变化保证枚举不越界。我在第一次学状态压缩时花了很长时间才理解(sub - 1) mask的美妙之处。后来回过头来想如果提前做过大量位运算基础题尤其是这种“只允许删除 1”的题目理解过程会顺畅很多。这也是为什么我建议刷题时不要只追求 AC而是尽量把每题背后的位运算模型沉淀下来。回到 3226 本身最后的经验总结也很简单看到“位更改次数”先确认方向看到“整数相等”先判断子集包含看到“1 的个数”先想到 popcount。把这三件事想明白代码怎么写都是水到渠成。实际提交时我第一次因为没加(n k) k就错了加上之后一次通过。从那以后我遇到位运算题都会先问自己一句这里允许 0 变 1 吗这个习惯帮我避开了很多同类陷阱也分享给你。