企业官网建设流程全解析

做这类构造题，最怕一上来就盯着“怎么把数组填出来”，结果被各种输出限制绕晕。LeetCode 3315《构造最小位运算数组 II》这道每日一题，输入是一个数组，输出也要求一个数组，核心却不在数组本身，而在每一位数字背后的二进制规律。我最早接触它的时候，第一反应是枚举，后来发现这题真正的考点是：你能不能从x | (x+1)这个操作的结果，反推出最小的 x。

这篇文章我会从题目拆解、位运算原理、代码实现、边界情况、对拍验证这几个角度完整讲一遍。无论是刚刷题的新手，还是想快速复习位运算套路的老手，都能在文章里找到可以直接抄走的东西。

1. 题目到底在问什么：先看懂x | (x+1)的脾气

1.1 一个数组输入、数组输出的构造题

先明确题面：给定一个非负整数数组nums，对数组里的每一个数字nums[i]，你需要构造出一个最小的非负整数x，使得x | (x+1) = nums[i]成立。如果这样的x不存在，对应位置返回-1。

也就是说，输出数组的每一位，都是根据输入数组对应位的那个数字反推出来的。输入[1, 3, 4]，输出可能是[0, 1, -1]，因为0 | 1 = 1，1 | 2 = 3，而找不到一个非负整数x能让x | (x+1) = 4。

构造题有个特点：它不像动态规划或图论那样需要状态转移，而是需要你找到一种“生成规则”。这题的关键，就是彻底看懂x | (x+1)这个位运算操作，到底对二进制的哪一位做了什么事情。

1.2 拆解x | (x+1)的底层行为

先拿几个小数字做实验：

• x = 0，二进制是0，x + 1 = 1，0 | 1 = 1
• x = 1，二进制是1，x + 1 = 2，二进制是10，01 | 10 = 11，也就是3
• x = 4，二进制是100，x + 1 = 5，二进制是101，100 | 101 = 101，也就是5
• x = 7，二进制是111，x + 1 = 8，二进制是1000，0111 | 1000 = 1111，也就是15

观察二进制的人会立刻发现一件事：x和x+1是连续的整数，它们除了最低那一段 1 会产生进位之外，更高位基本保持不变。异或运算能把两个数的差异位标出来，或运算则会把进位后新出现的 1 和原来低位的 1 全部保留。

所以x | (x+1)的结果，本质上就是一个“给最低位连续的 1 段向右扩展一位”的操作。如果x = 10111，它的低位连续 1 段长度是 3，那么x | (x+1)得到的结果，低位 1 段长度会变成 4，也就是101111的一部分。

1.3 用例子把规律钉死

为了确保规律没有偏差，我列一张对照表，把x、x+1、以及x | (x+1)的关系摆在一起看：

看到最后几行你应该有感觉了：结果的低位连续 1 段长度，永远比x的低位连续 1 段长度多 1。这是整个题目解题的钥匙。

2. 从结果反推：无解判定与答案构造公式

2.1 为什么偶数一定无解

先回答一个最直观的问题：什么样的n一定不存在对应的x？

因为x和x+1是连续的两个整数，它们一奇一偶。奇数二进制最低位是 1，偶数二进制最低位是 0。按位或之后，最低位只要有任意一个 1，结果就是 1。所以无论x是奇数还是偶数，x | (x+1)的结果最低位一定是 1。

换句话说，输入的n如果是个偶数，最低位是 0，那这个n根本就不可能是某个x | (x+1)的结果。这种情况直接返回-1就是正确答案。

这个结论非常简洁，但它省掉了大量无效的枚举。我在第一次做这道题时，就是先写了一个暴力循环，发现所有偶数都会在枚举到n之前失败，后来才意识到这不是偶然，而是位运算本身的必然。

2.2 低位连续 1 段长度 m 是唯一需要的东西

假设输入的n是奇数，那么它从最低位开始，有一段连续的 1。

比如n = 11，二进制是1011，最低位连续的 1 段长度是 2，也就是从第 0 位和第 1 位都是 1，第 2 位是 0；比如n = 7，二进制是111，低位连续 1 段长度是 3，而第 3 位是 0，或者说第 3 位已经超出二进制当前位数，可以认为它前面有一个隐藏的 0。

这个连续 1 段的长度就是题目反推的核心变量。设它为m，那么根据前面的规律，原始x的低位连续 1 段长度应该是m - 1，也就是说，x比n少了一个 1，而这个 1 是出现在“连续 1 段最高位”的。

举例来说，n = 1011，低位连续 1 段长度是 2，那x的低位连续 1 段长度就是 1。n里第 1 位是 1，x里第 1 位就必须变成 0，更高位保持不变，于是x = 1001 = 9。

再验证n = 7，低位连续 1 段长度是 3，x的低位连续 1 段长度就是 2，n里第 2 位是 1，x里第 2 位变成 0，所以x = 011 = 3。

2.3 统一公式：把连续 1 段的最高位清 0

于是答案公式变得非常简单：对于奇数n，先求出它从最低位开始的连续 1 段长度m，然后把n的第m - 1位（也就是这段连续 1 的最高位）从 1 变成 0，其他位全部不动，得到的就是最小的x。

写成位运算就是：

x = n ^ (1 << (m - 1))

因为n的第m - 1位本来就是 1，用异或可以把这一位翻转成 0，而其他位不受影响。

这里有一个容易绕晕的点：为什么是“把连续 1 段的最高位清 0”，而不是“把第 m 位变成 1”？

我一开始也犯过这个错。原因是，x | (x+1)的结果里，低位连续 1 段的长度虽然是m，但多出来的那个 1 不是靠“把n的第 m 位变成 1”得到的。n的第 m 位本身是 0，而结果里的这个 1 来自进位，原本在x的第 m 位那里是一个 0。真正发生变化的位置，是x的“连续 1 段最高位”，它会被x+1的进位清成 0，同时把下一个 0 位变成 1，再进行或运算后，低位原有的 1 全部保留。反推的时候，只需要把n里这段连续 1 的最高位还原成 0，其他位和n保持一样就行。

所以核心只有一句话：结果的低位连续 1 段长度，比原数的低位连续 1 段长度多 1。反推就是把这个多余的 1 去掉。

3. 代码实战：从暴力枚举到 O(1) 构造

3.1 用暴力验证公式的正确性

在写最终代码之前，我建议先写一个暴力版本，方便对拍验证。对于一个给定的n，直接从小到大枚举所有可能的x，检查x | (x+1)是否等于n。因为答案一定小于等于n，所以枚举范围控制在0到n就够。

def brute(n: int) -> int: for x in range(n + 1): if (x | (x + 1)) == n: return x return -1

这个暴力方法在n很小时完全没有问题，可以用来验证后面的公式是否正确。我在本地拿1到10000全部跑了一遍，公式和暴力的结果完全一致。

暴力的作用不是用来提交，而是用来建立信心。公式题最怕的就是自我感动式推导，写个对拍器一测，所有边界情况都暴露了。

3.2 C++ 参考实现

有了公式，正式代码就很短了。这里要处理一个关键步骤：如何求n的低位连续 1 段长度m。最稳妥的方法是循环右移，每遇到一个 1 就累加，遇到 0 或右移为 0 时停止。

#include <vector> using namespace std; class Solution { public: vector<int> minBitwiseArray(vector<int>& nums) { vector<int> ans; ans.reserve(nums.size()); for (int n : nums) { if ((n & 1) == 0) { ans.push_back(-1); continue; } int m = 0; int t = n; while (t & 1) { ++m; t >>= 1; } ans.push_back(n ^ (1 << (m - 1))); } return ans; } };

循环的次数最多也就是二进制位数，比如 32 位整数最多循环 31 次。对于单个数字来说可以看作 O(1)，整个数组的时间复杂度是 O(nums.size())。空间复杂度是 O(1)，除了返回结果之外没有额外的大结构。

3.3 Python 和位运算的细节差异

Python 版本的逻辑完全一样，但有一个非常容易踩的坑：Python 的整数没有固定位数，右移不会自动归零处理。好在这里我们只关心最低位的连续 1，所以逻辑依然简单。

def construct(nums): ans = [] for n in nums: if n % 2 == 0: ans.append(-1) continue m = 0 t = n while t & 1: m += 1 t >>= 1 ans.append(n ^ (1 << (m - 1))) return ans

Python 里需要注意，n & 1和n % 2对正整数来说等价，但前者更贴近位运算语义。另外1 << (m - 1)在m为 0 时会变成1 << -1，这是会报错的。但m为 0 只发生在n是偶数时，而那段在判断偶数时已经continue掉了，所以这里的m必然大于等于 1。

C++ 里如果用__builtin_ctz这类内置函数，代码可以更短，但有一个隐藏的风险，我放到下一节说。先记住一个原则：在竞赛中，简单清晰的循环永远不会错，炫技式的内建函数反而可能让你在边界上翻车。

4. 我踩过的坑：边界条件全集

4.1 最小输入和全 1 输入

先看n = 1的情况。n是奇数，低位连续 1 段长度m = 1，代入公式：

ans = 1 ^ (1 << 0) = 1 ^ 1 = 0

验证一下：0 | 1 = 1，而且0是最小的非负整数，所以答案正确。这个例子很容易被忽略，但它恰好验证了“最小的 x 可以是 0”。

再看全 1 输入，比如n = 7、n = 15、n = 31。这些数字的二进制全是 1，循环求m时，会一直右移到t变成 0 才停下。比如n = 7，二进制是111，t依次是111、11、1、0，循环次数是 3，得到m = 3。答案7 ^ (1 << 2) = 7 ^ 4 = 3，验证3 | 4 = 7，正确。

所以全 1 输入不需要单独判断，循环版本天然能处理。但如果你用某些内置函数，就要格外小心，因为全 1 数字的反码可能全是 0，导致内置函数行为未定义。

4.2__builtin_ctz的未定义行为陷阱

有的题解会写成这样：

int m = __builtin_ctz(~n); ans.push_back(n ^ (1 << (m - 1)));

ctz是 count trailing zeros，统计二进制末尾连续 0 的个数。对奇数n来说，~n的末尾连续 0 个数，恰好就是n的末尾连续 1 个数，所以这个写法理论上成立。

但问题在于：如果n是 int 类型中的全 1，也就是-1，那么~n = 0，ctz(0)是未定义行为。虽然在 LeetCode 的测试里不一定碰到-1，但这种写法有明显的隐患。

另一个坑是~n在高位会变成 1。对于形如n = 7的情况，~n在 32 位 int 中其实是11111111111111111111111111111000，末尾连续 0 的个数是 3，这没错。但如果n本身是0x7FFFFFFF这种 31 位全 1 的正数，~n的末尾连续 0 个数会变成 31，而按题意我们应该把第 30 位改成 0，两个结论就冲突了。

所以我的建议是：别在正式代码里用__builtin_ctz处理这个题，老老实实写 while 循环。

4.3 位运算优先级和类型转换

另一个容易出问题的地方是运算符优先级。比如：

ans.push_back(n ^ (1 << (m - 1)));

这里的右移和左移都要用括号包起来，尤其1 << (m - 1)不能写成1 << m - 1。在 C++ 里，<<的优先级低于加减法，所以1 << m - 1实际上会先算m - 1，看起来结果一样？其实 C++ 里移位运算符优先级比加减法低，所以1 << m - 1等于1 << (m - 1)，这个例子反而没问题。但为了可读性和防止在别的语言里翻车，我习惯所有位运算都加括号。

Python 里的优先级更反直觉：<<的优先级也低于加法减法，但高于比较运算符。如果不加括号，代码很难一眼读对。我的原则是：位运算和算术运算混在一起时，一律用括号标明顺序。

还有类型转换问题。LeetCode 的输入范围通常不超 int，但如果你把1 << (m - 1)用在超出 int 范围的场景，要考虑用1LL转成 long long。这道题正常不会需要，但养成习惯没坏处。

4.4 一组特殊输入速查表

我整理了一组测试用例，建议提交前全部跑一遍：

有了这个表，大部分边界情况都能覆盖到。

5. 测试与对拍：怎么确保答案真的最小

5.1 写一个独立对拍器

公式题最怕的不是思路错，而是“局部对但整体错”。所以我每次写完公式解，都会同步写一个暴力解，然后让它们随机对拍。

对拍器的逻辑很简单：生成随机测试数据，同时跑暴力版本和公式版本，逐个比较结果，一旦不一致就打印出来。下面是我用的 Python 对拍脚本：

import random def brute(n): for x in range(n + 1): if (x | (x + 1)) == n: return x return -1 def fast(n): if n % 2 == 0: return -1 m = 0 t = n while t & 1: m += 1 t >>= 1 return n ^ (1 << (m - 1)) for n in range(1, 20000): if brute(n) != fast(n): print(f"mismatch: {n}, brute={brute(n)}, fast={fast(n)}") break else: print("all ok")

这里没有用随机数据，而是直接从 1 到 19999 全覆盖。因为范围不大，暴力也跑得动。这样测试比纯随机更全面，不会漏掉少数边界。

5.2 用公式再反向验证

除了和暴力对拍，还可以做一层反向验证：对公式算出来的每个x，重新计算x | (x+1)，确认它等于输入的n，并且确认x小于等于n。这一步能抓住“构造出的数组满足条件”这个最基本的要求。

反向验证本质上是在做性质测试。刷题时我习惯在本地写这么一段：

def verify(nums): ans = construct(nums) for n, x in zip(nums, ans): if x != -1: assert (x | (x + 1)) == n, (n, x) assert x >= 0 return True

只有正向公式、暴力对拍、反向验证三关全过，我才会把代码提交。

5.3 性能压力测试

这道题的时间复杂度很低，就算nums有十万个元素，每个数字做一次常数级操作，也完全不会超时。但如果你在循环里用了笨办法，比如对每个n再套一层循环枚举，就会出问题。

我做了一个简单的性能测试：构造一个长度一百万的数组，里面随机生成一万以内的奇数偶数，然后跑公式版本，耗时在毫秒级。这是典型的 O(n) 题目，真正的考点从来不是性能，而是你能不能把二进制规律想清楚。

如果你在面试或者周赛里碰到这题，千万不要一上来就写双重循环。先举几个小例子观察规律，通常比硬想公式快得多。

6. 扩展视角：这一题背后通用的位运算套路

6.1 由结果反推输入的通用思路

这一类题有一个非常通用的模式：给你一个操作f(x)，再给你操作结果n，让你反推满足条件的最小x。解题套路通常是三步。

第一步，把操作f(x)理解成二进制层面的一次“形态变化”。不要盯着十进制数值看，而是把数拆成二进制位，看每一位如何变化。第二步，找到变化的“不变量”或者“增长规律”。比如这题里，低位连续 1 段长度加 1，其他位保持不变，就是一个非常清晰的不变量。第三步，从结果反推输入时，只需要把变化的那一步逆回去，其他位原样保留。

这个方法可以迁移到很多位运算题上，比如给定x & (x-1)的结果反推x，或者给定x ^ (x-1)的结果找 lowbit 规律。位运算题的题面千变万化，但底层都是类似的二进制形态变换。

6.2 这类“构造最小数组”的题目模式

LeetCode 的构造类题目有一个常见套路：给你一个目标值，要你构造一个结构（通常是数组）使得某种运算结果等于目标值，同时要求结构本身最小。

这里的“最小”有不同的定义，有时候是数组长度最短，有时候是字典序最小，有时候是单个数最小。本题就是单个数最小。遇到这种题，先别急着套贪心或者 DP，先看这个运算本身有没有“可逆性”。如果操作是可逆的，比如本题通过连续 1 段长度就可以反推，那构造就会非常简单；如果操作不可逆，比如或运算会丢失信息，才需要考虑贪心。

还有一个经验：构造题里出现“最小”两个字，答案往往和一个边界情况有关。本题的最小值是 0，因为x可以是 0；如果你推导出的最小候选值一直是正数，要回头检查是不是漏了 0 的情况。

6.3 系列题“II”带来的难度变化

题目标注了“II”，意味着前面大概率有一个“I”。系列题的升级方式通常有三种：数据范围变大、约束变复杂、从单点查询变成批量查询。

3315 这个第二版，我推测就是把原来给单个数构造的方式，变成了给整个数组批量构造。输入输出都变成数组后，题目的难度其实不在于单个数怎么算，而在于你需要在每个数上都能快速得出答案，不能对每个查询都进行一次重的搜索。所以 O(1) 的反推公式，在这种批量场景下就显得尤其重要。

如果你之前只做过“I”，碰到“II”的时候，先别慌。比较一下两版题面，找出新增的限制是什么，往往比从头想一个全新方案要快得多。我在周赛里遇到过好几次“II”比“I”只是把单次查询改成了多次查询，只要把单次 O(1) 的逻辑不变，边界处理干净，就能顺利通过。

这题做到最后，我个人最大的体会是：位运算的题目，不要靠“我感觉应该是这样”去写代码，一定要拿纸笔把二进制列出来，哪怕从 0 到 15 全部列一遍也不亏。很多规律不是想出来的，是看出来的。先写一个能跑的暴力版本，再在上面观察规律，最后推导公式，这个过程本身比这道题的 AC 更有价值。