1. 题目初印象这道题到底在问什么刷题群里有朋友发来一道题目链接题目编号是 3226名字叫“使两个整数相等的位更改次数”。乍一看“位更改次数”这个说法有点绕但把题目读一遍之后会发现它其实是在考察两个最基本的位运算能力判断某些二进制位是否满足条件以及统计二进制中 1 的个数。这道题本身不难但特别适合用来检查自己对位运算的理解是不是“真懂”而不是只会背模板。题目大意是这样的给定两个正整数 n 和 k每次操作可以选择 n 的二进制表示中的任意一个 1把它改成 0。问能否通过若干次这样的操作让 n 变成 k如果可以最少需要多少次操作如果不可以返回 -1。举个例子n 13二进制是 1101k 4二进制是 0100。13 可以先把第 3 位的 1从低位往高位数的第 3 位即 4 对应的那一位保留把第 1 位和第 4 位的 1 改成 0这样 1101 就变成了 0100也就是 4。一共改 2 次所以答案是 2。而如果 n 1k 2也就是 n 的二进制是 01k 的二进制是 10你会发现 n 里唯一的那个 1 在最低位而 k 需要的 1 在第二位。题目只允许把 1 改成 0不允许把 0 改成 1所以这种情况下无论怎么操作n 都不可能变成 k答案就是 -1。这道题适合什么人我觉得初级和中级水平的开发者都值得花十分钟做一遍。初级开发者可以通过它把“按位与”“异或”“内置位计数函数”这些基础概念串起来中高级开发者可以用它快速检验自己对位运算条件的敏感度——其实核心判断一句代码就写完了但很多人第一反应会写成循环逐位扫描倒不是说不行只是不够漂亮。2. 位运算基础先把四个运算符和两个概念焊死在脑子里要彻底吃透这道题必须先回到位运算的基本功上。这里我不打算把教科书抄一遍而是用我自己理解的方式把这道题真正用得上的几个点过一遍。2.1 按位与两个位都是 1 才是 1按位与的规则一句话“有 0 则 0全 1 才 1”。比如 1101 0100一位一位看第一位 100第二位 000第三位 111第四位 100结果是 0100。这玩意儿在生活中的类比可以是“门禁双人验证”——必须两个人都在两个位都是 1才算通过。而在这道题里按位与的作用非常重要如果我们用n k得到的结果表示“n 和 k 在哪些位上同时是 1”。如果(n k) k说明 k 中所有为 1 的位n 中也全部为 1。这里要多说一句为什么这个判断如此关键。题目只允许把 n 的 1 改成 0不允许把 0 改成 1。所以 n 要变成 k必须满足一个前提k 里有的 1n 里必须本来就有。如果 k 的某一位是 1但 n 的那一位是 0那就没有任何办法“生成”这个 1。(n k) k这个条件做的就是这件事把 n 和 k 逐位比对把“k 有的 1”全部挑出来看看 n 是不是都覆盖了。2.2 按位异或^相同为 0不同为 1异或的规则是两个位相同则结果为 0不同则结果为 1。它的一个经典应用就是“找不同”。n ^ k的结果里哪些位是 1就说明 n 和 k 在那一位上不一样。在这道题里一旦确认了可以变那 n 到 k 需要改多少个 1答案是n 中有 1 但 k 中没有 1 的那些位。因为题目限定只能改 1 为 0所以只需要关心 n 比 k “多出来”的 1。而 n 比 k 多的那些位在n ^ k中恰好会变成 1——因为 n 位是 1k 位是 0两数不同异或结果就是 1。所以答案可以直接写成popcount(n ^ k)。这其实比“数数 n 有几位 1再减去 k 有几位 1”更直觉也更好记。2.3 按位取反~与移位、先了解题目里不直接用~是按位取反把 0 变 1、1 变 0。在 32 位有符号整数的语境下~0的结果是 -1因为 0 的 32 位全是 0取反后全是 1而 32 位全是 1 的补码表示就是 -1。移位运算表示左移右边补 0表示右移对于无符号数或非负整数左边补 0。这道题 LeetCode 原题的整数是正整数所以不涉及负数移位的坑但后面做题多了会遇到先留个印象。2.4 内置函数__builtin_popcount 和 Integer.bitCount统计一个整数二进制里 1 的个数C 可以用__builtin_popcount(n)Java 是Integer.bitCount(n)Python 则是bin(n).count(1)或者从 Python 3.10 开始用int.bit_count()。这些都是解决本题“改了几次”这个问题的核心工具。如果不用内置函数手写统计也完全可以。最朴素的方式是循环 32 次每次用n 1取最低位然后n 1也可以用 Brian Kernighan 算法每次执行n (n - 1)来消除最低位的 1循环次数等于 1 的个数。后面的扩展部分我会专门写这个算法因为它的思路非常值得学习很多位运算题都能用到。3. 题目解法推导从“模拟规则”到“一句话判断”这道题初见的时候很多人会想那我能不能直接模拟操作每次找一个 1 改成 0用 BFS 或者 DFS 去搜最少步数可以但是完全没有必要因为规则里藏着一个很强的限制——只能把 1 改成 0。这个限制直接把问题的搜索空间压成了一个判断问题。3.1 第一步判断“可不可行”先看不可行的情况。假设 n 8二进制 1000k 3二进制 0011。k 的最低位和第二位都是 1但 n 只有第四位是 1剩下全是 0。你不可能把 n 的第四位 1 变成 0 后又变出一个 1 来填充低位所以这种情况直接返回 -1。怎么用代码表达这种判断最直观的写法是if ((n k) ! k) { return -1; }为什么不是n k ! k这里必须提一个特别容易踩的坑C 中的优先级低于!。如果不加括号n k ! k会被解析成n (k ! k)也就是n 0结果恒为 0整个判断就废了。我接触过的很多初学者在这里翻过车包括我自己早年也在这上面栽过所以记住位运算涉及混合表达式时别省括号。(n k) k这个条件还可以换种方式理解它等价于“k 是 n 的二进制子集”。在状态压缩动态规划里我们经常说“子集”这个词指的就是二进制表示中每个为 1 的位另一个数也有。判断子集的标准写法就是这个(a b) b。3.2 第二步计算“最少改几次”如果可行那最少操作次数怎么算换个角度想n 和 k 已经满足了“k 的每一位 1n 都有”这个条件那 n 中可能会多出一些位是 1而 k 是 0。这些多出来的 1 必须全部清成 0每一个这样的位就对应一次操作。有两种等价的算法计算n ^ k统计结果中 1 的个数。因为异或结果中为 1 的位恰好表示“n 和 k 在此位不同”在已经验证可行的情况下不同只可能是“n1 且 k0”。计算popcount(n) - popcount(k)。因为 k 的 1 都在 n 中出现了所以 n 的 1 的个数一定不小于 k 的 1 的个数差值就是多出来的位数。比如 n 131101k 40100。n ^ k的结果是 1001有 2 个 1所以答案是 2。用第二种方法n 有 3 个 1k 有 1 个 1差也是 2。两种方法我推荐优先用n ^ k因为只要一行代码而且语义更贴合“差异”这个概念return __builtin_popcount(n ^ k);3.3 完整代码C 版本class Solution { public: int minChanges(int n, int k) { if ((n k) ! k) { return -1; } return __builtin_popcount(n ^ k); } };Java 版本class Solution { public int minChanges(int n, int k) { if ((n k) ! k) { return -1; } return Integer.bitCount(n ^ k); } }Python 版本class Solution: def minChanges(self, n: int, k: int) - int: if (n k) ! k: return -1 return (n ^ k).bit_count()代码简单到有点像在写伪代码但这正是位运算题目的魅力只要思路对核心代码往往就是两三行。这道题的时间复杂度是 O(1)空间复杂度也是 O(1)——当然严格说__builtin_popcount在硬件指令下也是一两个周期的事情可以当作常数。4. 边界情况与易错点这些坑我替你们先踩过了做题和写工程代码一样最怕的不是主流程而是边界条件。这道题表面简单边界情况其实不少而且每一个都值得展开说说。4.1 k 0 怎么办当 k 0 时k 的二进制全是 0(n k) 0恒成立所以永远可行。此时答案等于把 n 中所有的 1 都清零也就是popcount(n)。用n ^ k算的话n ^ 0 n统计 n 的 1 个数结果一致。这个边界看起来不起眼但它是检验你代码健壮性的第一关。有些人的思路是“枚举 k 的每一位 1然后看 n 有没有”这种思路在 k0 时需要特殊处理而直接用(n k) k判断的话k0 天然满足完全不用额外写 if。4.2 n k 怎么办n 等于 k 时每一位都相同(n k) k成立n ^ k 0结果 0。这个边界很容易理解但很多人会忘记验证自己的解法在“已经相等”时输出 0而不是返回 -1 或者别的什么。其实只要代码写对了这个 case 自动通过不需要额外分支。4.3 题目给的是 32 位有符号整数吗LeetCode 原题的约束是 n 和 k 是正整数但在一些变种题里会出现“32 位有符号整数”的描述。如果涉及到负数情况就复杂了负数在补码表示下高位全是 1n ^ k的结果可能包含大量高位 1popcount的结果会变得很大。不过 3226 这题明确是正整数所以不需要过度担心。但如果读者自己改题、自己出测试用例请务必注意这一点——我见过有人把 LeetCode 的 3226 改造成负数版本结果发现操作次数远大于 32因为补码的高位 1 全算进去了那个场景就需要重新定义规则了。4.4 运算符优先级位运算括号不能省前面说过n k k会被解析成n (k k)也就是n 1只保留了最低位。这个问题在 C/C 和 Java 里都会出现Python 的优先级规则略有不同但建议不管什么语言都养成加括号的习惯。这个小细节在面试手写代码时尤其重要因为面试官一定会盯着这类“看起来能跑但实际是错的”代码。4.5 输出 -1 的时机先判断还是先计数还有人会把顺序写反先算popcount(n ^ k)然后发现结果不对再补一个判断。这样不是说不行但逻辑上绕了一层。正确姿势是先判断可行性再计数。因为如果不可行n ^ k的结果没有语义——它混合了“n 有 k 没有”和“k 有 n 没有”两种情况你没法从总数里区分。我实际刷题时的经验是遇到这类“位运算 判断 计数”的题先写注释把规则列清楚再落代码。比如我会写// 1. k 必须是 n 的二进制子集否则 -1 // 2. 答案是 n 比 k 多出来的 1 的个数这不是形式主义而是防止自己写着写着忘记规则的廉价保险。4.6 大数据下的溢出思考n ^ k结果的范围是 0 到大约 2^31 - 1统计 1 的个数不会溢出。但如果有人在实现时写int ans 0; while (diff) { if (diff 1) ans; diff 1; }那要注意diff如果是 int 且为负数时右移会进行算术右移高位补 1导致死循环。再次强调这题是正整数没有这个问题但如果题目描述改成“整数”而不是“正整数”就要把类型改成无符号整数或者直接使用内置的bitCount。5. 同类题型与升级套路从一道题学会一类题做完 3226 之后我建议顺着位运算这条线继续刷几个相关的题目因为它们之间是层层递进的。把这些题放在一起看你会发现所谓的“新题”其实只是老套路的组合变体。5.1 汉明距离异或之后统计 1 的个数LeetCode 461“汉明距离”问的是两个整数二进制位不同的个数。解法就是Integer.bitCount(x ^ y)。这和 3226 的核心步骤完全一致异或找差异popcount 数差异。区别只在 3226 多了一步“可行性判断”因为题目操作方向受限不能随便把 0 改 1。学习建议先把 461 做熟再回来做 3226你会觉得水到渠成。5.2 只出现一次的数字异或的“消消乐”性质LeetCode 136“只出现一次的数字”给一个数组里面所有元素都出现两次只有一个出现一次找出它。解法是把所有元素异或起来出现两次的数字在异或中抵消为 0最后剩下的就是答案。异或的这个性质——“相同为 0不同为 1”看起来简单但在实际问题里极其好用。3226 里用异或来找 n 和 k 的差异本质就是用了它的“对比”能力而 136 里则用了它的“抵消”能力。同一个运算符不同的语义侧重点这是位运算最有意思的地方。5.3 2 的幂判断n 0 且 (n (n - 1)) 0LeetCode 231“2 的幂”让判断一个整数是否是 2 的幂次。一个数如果是 2 的幂它的二进制只有一个 1比如 1、2、4、8 对应 1、10、100、1000。此时n (n - 1)会把这个唯一的 1 消掉结果是 0。这个技巧和 3226 的关系在于它们都用到了“二进制中 1 的分布”这个视角。5.4 Brian Kernighan 算法循环次数等于 1 的个数如果要自己手写统计 1 的个数Brian Kernighan 算法是我最推荐的写法int countOnes(int x) { int cnt 0; while (x) { x (x - 1); // 消去最低位的 1 cnt; } return cnt; }这个算法的原理非常巧妙x - 1会把 x 最低位的 1 变成 0同时把它右边的 0 全部变成 1比如x 1010020x - 1 1001119两者相与得到1000016——最低位的 1 被消掉了。循环次数正好等于二进制中 1 的个数平均性能比逐位扫描好尤其在二进制中 1 的个数较少时优势明显。5.5 状态压缩 DP位运算的大显身手之地3226 只是一个引子真正的位运算大场景在状态压缩动态规划比如旅行商问题、子集枚举等。这类问题里一个整数的二进制位被当作一个集合来用第 i 位是 1 表示第 i 个元素被选中。判断一个集合 A 是否包含另一个集合 B用的正是(A B) B这个子集判断。所以我说 3226 是“基础中的基础”——它把子集判断这个在状态压缩里反复使用的操作单独拿出来包装成了一道看起来很人畜无害的简单题。6. 面试与工程场景位运算为什么值得多花时间有人会问现在开发都写业务代码位运算好像用不太上这个观点我部分同意但也不完全同意。业务开发中确实很少直接操作二进制位但位运算的思路会渗透到很多底层设计和性能敏感场景里。6.1 面试考察点基本功的试金石在算法面试中位运算类题目出现频率不算超高但属于“一旦出现就能拉开差距”的题目。不是因为位运算本身有多难而是很多人平时根本不接触遇到时容易懵。3226 这种题目就是典型的考查点它不会要求你写复杂算法但它能够检测出你是否熟悉、^、bitCount这些基础工具以及你是否具备“把一个操作规则转化成位运算表达式”的能力。面试的时候如果遇到这题我建议按下面这个节奏来先把规则口头重复一遍尤其强调“只能 1 变 0”。说出核心判断(n k) k并解释为什么。说出计数方案bitCount(n ^ k)并解释异或结果中 1 的含义。最后再补一句时空复杂度。这样一套下来面试官会认为你不仅会写代码而且思路是清晰的不是背答案。6.2 工程场景中的实例权限系统与标志位工程代码里最经典的位运算应用之一是权限系统。假设一个系统有四种权限读、写、执行、管理。用四个二进制位表示比如0001表示可读0010表示可写0100表示可执行1000表示管理。某个用户拥有读和执行权限那么他的权限值就是0001 | 0100 0101。判断用户是否拥有写权限(permission 0b0010) ! 0。追加一个权限permission | 0b0010。收回一个权限permission ~0b0010。这些操作本质上和 3226 里面做的事情是同一类用位向量表示集合用位运算操作集合。6.3 性能敏感场景状态压缩与位图在网络协议、数据库索引、缓存标记等高性能场景里位图Bitmap是常见的数据结构。它可以用来标记大量对象是否存在每个对象只占用 1 bit内存效率极高。而操作位图时判断、更新、统计都依赖位运算。如果你能熟练掌握、|、^、~、、以及 popcount 这类操作阅读和编写底层代码会轻松很多。7. 实战心得从“看懂题解”到“自己写得出来”最后聊一点我做这类题目的感受。题目容易但如果只是看完题解点点头那下次见到变种还是会卡壳。我自己的经验是遇到位运算题一定要亲手在纸上把二进制的演变过程写一遍。比如 n13、k4 这组数据我会写n 1101 k 0100 nk 0100 n^k 1001写完之后你会发现(nk)k之所以成立正是因为 0100 的每一位都是 n 中已有的n^k的 1001 则是 n 里多出来的两个 1。这种手工演算的效果远超过直接抄代码因为你会慢慢形成“看到二进制就自动拆位”的感觉。另一个建议是善用内置函数但也要能手写。Integer.bitCount确实方便可如果只是为了用而用不理解它底层做的事情遇到“不能用内置函数”的限制有些面试官会故意设这种限制你就慌了。把 Brian Kernighan 算法写熟练几十秒就能手写出来这才是自己的东西。关于题目本身我还想再补充一个很多人没注意到的点minChanges这个名字里的 “min” 其实是一种干扰信息。一旦满足了可行性条件操作次数是唯一的根本不需要“最小化”。所以这道题的真正难点不是“最小化”而是“判断是否可行”。想通这一点整个题就从“搜索题”降级成了“判断题”代码量自然减下来了。最后分享一个刷题时的小技巧如果你做过 LeetCode 191位 1 的个数、461汉明距离、2312 的幂这几道题再来看 3226你会发现它就是把 461 加了一个(n k) k的前置判断。平时刷题时多整理这种“套路之间”的联系比单纯堆题目数量有用得多。至少对我来说这种“原来这个新考点是老知识点的组合”的感觉才是刷题最上头的瞬间。