企业官网建设流程全解析

1. 题目初印象：这道题到底在问什么

刷题群里有朋友发来一道题目链接，题目编号是 3226，名字叫“使两个整数相等的位更改次数”。乍一看“位更改次数”这个说法有点绕，但把题目读一遍之后会发现，它其实是在考察两个最基本的位运算能力：判断某些二进制位是否满足条件，以及统计二进制中 1 的个数。这道题本身不难，但特别适合用来检查自己对位运算的理解是不是“真懂”，而不是只会背模板。

题目大意是这样的：给定两个正整数 n 和 k，每次操作可以选择 n 的二进制表示中的任意一个 1，把它改成 0。问能否通过若干次这样的操作，让 n 变成 k？如果可以，最少需要多少次操作；如果不可以，返回 -1。

举个例子：n = 13，二进制是 1101；k = 4，二进制是 0100。13 可以先把第 3 位的 1（从低位往高位数的第 3 位，即 4 对应的那一位）保留，把第 1 位和第 4 位的 1 改成 0，这样 1101 就变成了 0100，也就是 4。一共改 2 次，所以答案是 2。

而如果 n = 1，k = 2，也就是 n 的二进制是 01，k 的二进制是 10，你会发现 n 里唯一的那个 1 在最低位，而 k 需要的 1 在第二位。题目只允许把 1 改成 0，不允许把 0 改成 1，所以这种情况下无论怎么操作，n 都不可能变成 k，答案就是 -1。

这道题适合什么人？我觉得初级和中级水平的开发者都值得花十分钟做一遍。初级开发者可以通过它把“按位与”“异或”“内置位计数函数”这些基础概念串起来；中高级开发者可以用它快速检验自己对位运算条件的敏感度——其实核心判断一句代码就写完了，但很多人第一反应会写成循环逐位扫描，倒不是说不行，只是不够漂亮。

2. 位运算基础：先把四个运算符和两个概念焊死在脑子里

要彻底吃透这道题，必须先回到位运算的基本功上。这里我不打算把教科书抄一遍，而是用我自己理解的方式，把这道题真正用得上的几个点过一遍。

2.1 按位与（&）：两个位都是 1 才是 1

按位与的规则一句话：“有 0 则 0，全 1 才 1”。比如 1101 & 0100，一位一位看：第一位 1&0=0，第二位 0&0=0，第三位 1&1=1，第四位 1&0=0，结果是 0100。

这玩意儿在生活中的类比可以是“门禁双人验证”——必须两个人都在（两个位都是 1），才算通过。而在这道题里，按位与的作用非常重要：如果我们用n & k，得到的结果表示“n 和 k 在哪些位上同时是 1”。如果(n & k) == k，说明 k 中所有为 1 的位，n 中也全部为 1。

这里要多说一句为什么这个判断如此关键。题目只允许把 n 的 1 改成 0，不允许把 0 改成 1。所以 n 要变成 k，必须满足一个前提：k 里有的 1，n 里必须本来就有。如果 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 位是 1，k 位是 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（二进制 1000），k = 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 的每一位 1，n 都有”这个条件，那 n 中可能会多出一些位是 1，而 k 是 0。这些多出来的 1 必须全部清成 0，每一个这样的位就对应一次操作。

有两种等价的算法：

• 计算n ^ k，统计结果中 1 的个数。因为异或结果中为 1 的位，恰好表示“n 和 k 在此位不同”；在已经验证可行的情况下，不同只可能是“n=1 且 k=0”。
• 计算popcount(n) - popcount(k)。因为 k 的 1 都在 n 中出现了，所以 n 的 1 的个数一定不小于 k 的 1 的个数，差值就是多出来的位数。

比如 n = 13（1101），k = 4（0100）。n ^ k的结果是 1001，有 2 个 1，所以答案是 2。用第二种方法：n 有 3 个 1，k 有 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 有没有”，这种思路在 k=0 时需要特殊处理；而直接用(n & k) == k判断的话，k=0 天然满足，完全不用额外写 if。

4.2 n = k 怎么办

n 等于 k 时，每一位都相同，(n & k) == k成立，n ^ k = 0，结果 0。这个边界很容易理解，但很多人会忘记验证自己的解法在“已经相等”时输出 0，而不是返回 -1 或者别的什么。其实只要代码写对了，这个 case 自动通过，不需要额外分支。

4.3 题目给的是 32 位有符号整数吗

LeetCode 原题的约束是 n 和 k 是正整数，但在一些变种题里会出现“32 位有符号整数”的描述。如果涉及到负数，情况就复杂了：负数在补码表示下高位全是 1，n ^ k的结果可能包含大量高位 1，popcount的结果会变得很大。不过 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)) == 0

LeetCode 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 = 10100（20），x - 1 = 10011（19），两者相与得到10000（16）——最低位的 1 被消掉了。循环次数正好等于二进制中 1 的个数，平均性能比逐位扫描好，尤其在二进制中 1 的个数较少时优势明显。

5.5 状态压缩 DP：位运算的大显身手之地

3226 只是一个引子，真正的位运算大场景在状态压缩动态规划，比如旅行商问题、子集枚举等。这类问题里，一个整数的二进制位被当作一个集合来用：第 i 位是 1 表示第 i 个元素被选中。判断一个集合 A 是否包含另一个集合 B，用的正是(A & B) == B这个子集判断。所以我说 3226 是“基础中的基础”——它把子集判断这个在状态压缩里反复使用的操作单独拿出来，包装成了一道看起来很人畜无害的简单题。

6. 面试与工程场景：位运算为什么值得多花时间

有人会问，现在开发都写业务代码，位运算好像用不太上？这个观点我部分同意，但也不完全同意。业务开发中确实很少直接操作二进制位，但位运算的思路会渗透到很多底层设计和性能敏感场景里。

6.1 面试考察点：基本功的试金石

在算法面试中，位运算类题目出现频率不算超高，但属于“一旦出现就能拉开差距”的题目。不是因为位运算本身有多难，而是很多人平时根本不接触，遇到时容易懵。3226 这种题目就是典型的考查点：它不会要求你写复杂算法，但它能够检测出你是否熟悉&、^、bitCount这些基础工具，以及你是否具备“把一个操作规则转化成位运算表达式”的能力。

面试的时候如果遇到这题，我建议按下面这个节奏来：

1. 先把规则口头重复一遍，尤其强调“只能 1 变 0”。
2. 说出核心判断：(n & k) == k，并解释为什么。
3. 说出计数方案：bitCount(n ^ k)，并解释异或结果中 1 的含义。
4. 最后再补一句时空复杂度。

这样一套下来，面试官会认为你不仅会写代码，而且思路是清晰的，不是背答案。

6.2 工程场景中的实例：权限系统与标志位

工程代码里最经典的位运算应用之一是权限系统。假设一个系统有四种权限：读、写、执行、管理。用四个二进制位表示，比如0001表示可读，0010表示可写，0100表示可执行，1000表示管理。某个用户拥有读和执行权限，那么他的权限值就是0001 | 0100 = 0101。

判断用户是否拥有写权限：(permission & 0b0010) != 0。追加一个权限：permission |= 0b0010。收回一个权限：permission &= ~0b0010。这些操作本质上和 3226 里面做的事情是同一类：用位向量表示集合，用位运算操作集合。

6.3 性能敏感场景：状态压缩与位图

在网络协议、数据库索引、缓存标记等高性能场景里，位图（Bitmap）是常见的数据结构。它可以用来标记大量对象是否存在，每个对象只占用 1 bit，内存效率极高。而操作位图时，判断、更新、统计都依赖位运算。如果你能熟练掌握&、|、^、~、<<、>>以及 popcount 这类操作，阅读和编写底层代码会轻松很多。

7. 实战心得：从“看懂题解”到“自己写得出来”

最后聊一点我做这类题目的感受。

题目容易，但如果只是看完题解点点头，那下次见到变种还是会卡壳。我自己的经验是：遇到位运算题，一定要亲手在纸上把二进制的演变过程写一遍。比如 n=13、k=4 这组数据，我会写：

n = 1101 k = 0100 n&k = 0100 n^k = 1001

写完之后你会发现，(n&k)==k之所以成立，正是因为 0100 的每一位都是 n 中已有的；n^k的 1001 则是 n 里多出来的两个 1。这种手工演算的效果远超过直接抄代码，因为你会慢慢形成“看到二进制就自动拆位”的感觉。

另一个建议是：善用内置函数，但也要能手写。Integer.bitCount确实方便，可如果只是为了用而用，不理解它底层做的事情，遇到“不能用内置函数”的限制（有些面试官会故意设这种限制），你就慌了。把 Brian Kernighan 算法写熟练，几十秒就能手写出来，这才是自己的东西。

关于题目本身，我还想再补充一个很多人没注意到的点：minChanges这个名字里的 “min” 其实是一种干扰信息。一旦满足了可行性条件，操作次数是唯一的，根本不需要“最小化”。所以这道题的真正难点不是“最小化”，而是“判断是否可行”。想通这一点，整个题就从“搜索题”降级成了“判断题”，代码量自然减下来了。

最后分享一个刷题时的小技巧：如果你做过 LeetCode 191（位 1 的个数）、461（汉明距离）、231（2 的幂）这几道题，再来看 3226，你会发现它就是把 461 加了一个(n & k) == k的前置判断。平时刷题时多整理这种“套路之间”的联系，比单纯堆题目数量有用得多。至少对我来说，这种“原来这个新考点是老知识点的组合”的感觉，才是刷题最上头的瞬间。