企业官网建设流程全解析

LeetCode 3315 构造最小位运算数组 II，名字很长，内容很短：给你一个 target 数组，让你造一个 ans 数组，使得每个下标 i 都满足ans[i] | (ans[i] + 1) == target[i]，凑不出来的就填 -1。我最初看到题名里的 “II”，心里已经默认这是个要练位运算的题，第一版暴力提交果然超时。但真正让我觉得值得写一篇笔记的，是它的答案规律清爽到令人意外：一个数如果有解，答案就是把它二进制里最低位那串连续 1 的最高一位改成 0，几行代码搞定。下面把从读题、推规律、证明到编码踩坑的完整过程重新走一遍，适合正在刷周赛、专攻位运算或者想系统整理数组构造题解法的朋友。

1. 先确认题目到底在问什么：题面拆解与第一印象

1.1 题面到底在求什么：一条等式和一个 -1

给定长度为 n 的数组 target，要求返回等长的答案数组 ans。关键等式只有一个：ans[i] | (ans[i] + 1) == target[i]。这里的|是按位或，不是逻辑或；运算时先算ans[i] + 1，再与原值做按位或。如果某个位置不存在符合条件的整数，结果里填 -1。

这里有几个细节容易被忽略。第一，ans[i]不要求一定是正数，0 是允许出现的合法答案。第二，题目叫“构造最小位运算数组”，说明满足条件的解可能不止一个，我们要从中选出最小的那个。这个“最小”不是摆设，后面我们会看到同一个 target 值确实可能对应好几个不同的 x，选错一个就错一题。第三，整个题的本质是一个“反构造”过程：根据输出反推输入。

我一开始的思路非常直接：对每个 target[i]，从 0 开始枚举 x，逐个验证x | (x + 1) == target[i]，找到第一个满足的就是最小解。这个思路在上一题可能还行，到了 II 就不行了。

1.2 为什么“II”直接判了暴力枚举死刑

“II”是同一道题的加强版。上一题 LeetCode 3314 数据范围很温和，暴力枚举足够通过；到了这一题，出题人把约束往上抬了一个量级。具体是多少我不太记得，但大概方向是：target 数组长度可以到 10 万级别，单个 target 值可以到 10^9 级别。

假设只有长度是 10^5、单值是 10^9，每个元素都从 0 枚举到 target[i]，总操作量就是 10^14 这个数量级，绝不可能在规定时间内跑完。就算你只枚举到一半，也会被后面的数据点卡死。所以每处理一个元素必须要在 O(1) 或者接近 O(1) 的时间内算出答案，整体做到 O(n)。这逼着你去研究位运算本身的规律，而不是靠搜索引擎翻答案。

1.3 先把 x | (x+1) 翻译成人话

在推公式之前，我习惯先拿一个实际的二进制数算一算，搞清楚这个运算到底对 x 做了什么。

取 x = 9，二进制是1001。x + 1 = 10，二进制是1010。两者按位或：

1001 1010 ---- 1011

结果就是 11。观察这个过程：x 从最低位往高位数，第一个 0 出现在第 1 位（因为1001最低位是 1，第二位是 0）。x + 1 会发生进位：最低位的 1 进上来，把这一位变成 1，同时低位全部清成 0。再和原数 x 做按位或，这一位本来就是 1，低位原本是 1 的也还是 1。于是结果就是：把 x 二进制中最低位的那个 0 改成 1，比它更低的位保持原来的 1 不动，更高位完全不变。

再试一个最简单的：x = 8，二进制1000。最低位的 0 就是第 0 位，x + 1 = 9，二进制1001，或完还是1001= 9。同样是把最低位 0 改成 1。

所以x | (x+1)可以理解成一句话：在 x 的二进制表示中，找到最低位的 0，把它翻成 1，更低的部分因为本来全是 1，所以“顺手”保留。这个观察是整道题的命门，后面的所有推导都从这里来。

2. 从例子找规律：三分钟推出答案公式

2.1 先列一张“目标值->答案”的二进制小表

我推导这类问题有个习惯：先不空想，直接把小范围内的数据全部算出来，摆在面前找感觉。把 x 从 0 到 15 代入x | (x+1)，可以得到一张表：

这张表信息量很大。首先，所有结果都是奇数，没有一个偶数。其次，同一个结果会对应多个 x，比如 7 可以由 x=3、5、6 三个数得到；15 可以由 x=7、11、13、14 得到。这说明了“最小”并不是摆设。第三，结果的二进制形态非常有规律：它总是一段从低位开始的连续 1，有时候延伸到更高的位上。

现在反过来看题目，我们是以 target 为输入，反推最小的 x。把 target 记为 t，最低位连续 1 的个数记为 m。比如 t=1（1），m=1；t=3（11），m=2；t=5（101），m=1；t=7（111），m=3。列一张“t 到求出来的最小 x”的表：

偶数的情况先放一边，显然都是 -1。奇数的规律已经按不住：答案几乎都是t - 2^(m-1)。拿 23 验证：23 的二进制是10111，最低连续 1 是 3 个，m=3，23 - 2^2 = 19。19 的二进制是10011，19 | 20 =10011 | 10100 = 10111= 23。成立。

2.2 规律浮现：答案 = t - 2^(m-1)

把这个规律写成公式就是：

ans = t - 2^(m-1)

其中 m 表示 t 的二进制表示里，从最低位开始连续出现了多少个 1。

举个例子，t=13，二进制1101，最低位连续 1 只有 1 个，m=1，答案就是 13 - 1 = 12。t=15，二进制1111，最低位连续 1 有 4 个，m=4，答案是 15 - 8 = 7。所有奇数 t 都满足这个公式，偶数一律无解。

为什么偶数无解？很简单：看最低位。如果 x 最低位是 0，那么 x+1 最低位是 1，或完之后最低位是 1；如果 x 最低位是 1，x+1 会进位，最低位变成 0，但 x 自己最低位还是 1，或完之后最低位仍然是 1。所以无论 x 是什么，x | (x+1)的结果最低位永远是 1，也就是说结果永远是奇数。target 为偶数时，直接返回 -1，不需要再往下算。

2.3 一个 target 可以对应多个 x，最小解藏在公式里

从 2.1 那张表已经能看到，同一个 target 通常不只有一个来源。比如 target=7，x=3、5、6 都能生成 7；target=15，x=7、11、13、14 都能生成 15。如果我们从大到小枚举 x，第一个找到的常常是较大的解，不是题目要的最小值。

所以公式t - 2^(m-1)是不是真的对应最小解？拿 7 验证：7 的 m=3，7 - 4 = 3，确实是三个合法解里最小的那个。15 的 m=4，15 - 8 = 7，也是四个合法解里最小的。看起来公式给的正是最小值，而不是随便一个合法解。为什么偏偏是它？下一节用位级推导来解释。

3. 位级推导：为什么答案是 t - 2^(m-1)

3.1 设 k 为 x 最低的 0 位：x 到 t 只改了一位

回到 1.3 的结论：x | (x+1)的作用是找到 x 二进制里最低位的 0，记为第 k 位，把它翻成 1；低于 k 的位本来全是 1，保持为 1；高于 k 的位原样保留。

这句话反过来理解：如果x | (x+1) == t，那么 x 和 t 的差别只可能在一个位置上。具体来说，x 的第 k 位是 0，而 t 的第 k 位是 1；低于 k 的位，x 和 t 全是 1，完全相同；高于 k 的位，x 和 t 也完全相同。换句话说，x 就是把 t 的某一位 1 改写成 0，并且这个改写位置之下的所有位都是 1，保证改写时不会发生借位。

这个视角非常关键。x 不需要被理解成一个从 0 开始凑出来的数，它就是 t 做了一个“局部手术”的结果：把第 k 位的 1 改成 0，其他位原封不动。

3.2 候选 k 的范围：为什么是 0 到 m-1

现在要知道 k 可以取哪些值。

因为 x 第 k 位必须是 0，而 t 第 k 位必须是 1，所以 t 的第 k 位一定得是 1。t 从最低位开始连续有 m 个 1，分布在位置 0 到 m-1 上。于是 k 只能在 0 到 m-1 之间取。

反过来，只要 k 在 0 到 m-1 之间，比 k 更低的位（也就是 0 到 k-1 位）在 t 里一定全为 1，这正好满足“x 低于 k 位全是 1”的前提。而高于 k 的位，x 保持和 t 一样即可。所以每个 k = 0, 1, ..., m-1 都对应一个合法的 x，并且这个 x 就等于：

x = t - 2^k

因为只是把 t 的第 k 位从 1 改成 0，其他位没动，而且低位全 1，不会出现借位。

拿 t=7 来验证：m=3，k 可以取 0、1、2，对应的 x 分别是 7-1=6、7-2=5、7-4=3。正是那张表里看到的三个合法解。

3.3 从 t - 2^k 里挑最小：k 取最大合法值

既然每个合法解都是t - 2^k，要让 x 最小，就要让减掉的2^k最大。指数 k 越大，2^k越大，x 就越小。k 的合法范围是 0 到 m-1，最大就是 m-1。

所以最小解就是：

x = t - 2^(m-1)

这就把公式完全解释清楚了。它不是碰巧成立的规律，而是从“x 是 t 的某一位 1 被改成 0”这个基本事实推出来的必然结果。

3.4 全 1 边界例如 7、15 依然成立

再处理一个容易纠结的边界：如果 t 本身就是全 1 的数，比如 3、7、15、31 这种2^b - 1的形式，m 就等于它的二进制位数。公式依然成立。

以 7 为例，二进制111，m=3，答案 7 - 4 = 3。以 15 为例，二进制1111，m=4，答案 15 - 8 = 7。这种情况下“第 m 位”其实已经超过 t 的有效二进制长度，可以认为更高一位天然是 0，正好符合条件。所以公式不需要额外加特判。

整个推导最终浓缩成三步：判断是否为偶数；如果是奇数，数出最低连续 1 的个数 m；返回t - 2^(m-1)。代码量非常小，但每一步都有位级逻辑撑着。

4. 落地成代码：三种语言的完整实现

4.1 C++ 完整解法与注释

推导完成之后，写代码就是照搬公式。C++ 版本我写得比较啰嗦，但每一步都对应刚才的分析：

class Solution { public: vector<int> minBitwiseArray(vector<int>& nums) { int n = nums.size(); vector<int> ans(n); for (int i = 0; i < n; ++i) { int t = nums[i]; // 偶数无解，直接 -1 if ((t & 1) == 0) { ans[i] = -1; continue; } // 数出最低连续 1 的个数 m // 这里一定复制一份 cur，不要直接把 t 右移，后面还要用原始 t 做减法 int cur = t; int m = 0; while (cur & 1) { ++m; cur >>= 1; } // 把 t 的最低连续 1 中最高的一位改成 0 ans[i] = t - (1 << (m - 1)); } return ans; } };

有两点值得注意。第一，cur = t这一步不能省。如果在 while 里直接右移 t，循环结束后 t 已经被改成 0，后面的减法就会算错。第二，1 << (m - 1)在 m 为 0 时会产生非法移位，但因为我们提前判了奇数，m 至少为 1，所以这里是安全的。如果你担心后续数值范围变大，可以把1改成1LL，算完再转回 int。

4.2 Java 版本的两个细节

Java 写法和 C++ 几乎一样，唯一要留意的是左移的溢出问题。题目常规约束下 int 够用，但谨慎起见，我用1L做左移，再强转回 int：

class Solution { public int[] minBitwiseArray(int[] nums) { int[] ans = new int[nums.length]; for (int i = 0; i < nums.length; ++i) { int t = nums[i]; if ((t & 1) == 0) { ans[i] = -1; continue; } int m = 0; // 不修改 t 的写法：用 t>>m 来探测 while (((t >> m) & 1) == 1) { ++m; } ans[i] = (int) (t - (1L << (m - 1))); } return ans; } }

这里我没有复制 cur，而是通过t >> m来探测第 m 位是否为 1。这个写法更安全，也更紧凑。m 从 0 开始，第 0 位是 1，m 变为 1；再探测第 1 位，如果还是 1，m 继续加，直到遇到 0 为止。

4.3 Python 版本与整数注意事项

Python 写起来最简洁。Python 的整数没有固定位数，左移不用担心 int 溢出，但要注意位运算优先级和负数移位。本题所有数都是正数，所以用最简单的方式：

from typing import List class Solution: def minBitwiseArray(self, nums: List[int]) -> List[int]: ans = [] for t in nums: # 偶数无解 if t % 2 == 0: ans.append(-1) continue # 计算最低连续 1 的个数 m = 0 cur = t while cur & 1: m += 1 cur >>= 1 # 公式：t - 2^(m-1) ans.append(t - (1 << (m - 1))) return ans

Python 里while cur & 1:在 cur 为正数时不会陷入死循环，因为右移最终会把 cur 变成 0。但如果你把 t 改成负数，右移行为和 C++ 不一样，Python 算术右移会保留符号位，可能永远满足& 1，所以在 Python 里处理负数位运算时要格外小心。好在本题数据都是正数，不涉及这个问题。

4.4 自测函数：验证随机数据不出错

写完代码别急着提交，我习惯先写一个本地 check 函数：

bool check(int t, int x) { return (x | (x + 1)) == t; }

然后用测试数组整体跑一遍：nums = {1, 3, 5, 7, 2, 11, 13, 15, 21, 23}，期望输出{0, 1, 4, 3, -1, 9, 12, 7, 20, 19}。这里面包含了偶数无解、m=1、m=2、m=3、m=4 的各种情况。

更推荐的做法是写一个随机测试：随机生成若干个奇数 t，代入公式求出 x，再用 check 函数验证。如果所有随机样例都能通过，代码基本就稳了。这一步花不了多少时间，但能避免很多脑补失误。

5. 实战排雷：把常见错误和调试经验整理成清单

5.1 坑一：右移完忘了保留原始 t

这是最经典的错误。有人会把“数 m”和“算答案”写在一起：

int m = 0; while (t & 1) { ++m; t >>= 1; } ans[i] = t - (1 << (m - 1)); // t 已经被移成 0

当 t 右移结束后，t 早就不是原始值了。比如 t=13，右移第一次：13 >> 1 = 6，第二次：6 & 1 = 0，循环结束，此时 t=6，答案变成了 6 - 1 = 5，完全错误。正确做法是开头先int cur = t;，或者用 4.2 里那种((t >> m) & 1)的探测写法，始终保留原始 t 用于最后减法。

5.2 坑二：把 m 算成 0 导致非法移位

如果判断条件写反，比如：

int m = 0; while ((t & 1) == 0) { ++m; t >>= 1; } ans[i] = t - (1 << (m - 1));

对于偶数 t，循环会一直执行到 t 变成 0，m 可能很大；对于奇数 t，m 一开始就是 0，后面1 << (m - 1)变成1 << -1，在 C++ 里是未定义行为，在 Java 里会得到奇怪的负数值。所以进入计算前必须判奇数，确保 m 至少为 1。判断的方式很简单：(t & 1) == 0就先填 -1 并 continue。

5.3 坑三：以为从 t-1 往前枚举能拿最小值

还有一个隐蔽的思维误区：既然解不唯一，那我从 t-1、t-2 往下找，找到第一个满足条件的 x 就返回。这种写法有两个问题。第一是复杂度不可控，target 如果是 10^9 级别，最坏情况下要试很多次。第二是方向反了：从大往小找，找到的第一个满足条件的解其实是最大的合法解，而题目要的是最小解。以 t=7 为例，从 6 开始找，6 满足条件就直接返回 6，但正确答案是 3。如果你真想暴力，应该从 0 往上找，但那样又必然超时。所以暴力思路在本题两头不讨好，公式才是正路。

5.4 调试技巧：打印二进制 + 批量 check

调试这类位运算题，我最推荐的技巧是打印二进制。比如写一个辅助函数：

void printBinary(int x) { for (int b = 31; b >= 0; --b) { cout << ((x >> b) & 1); if (b % 4 == 0) cout << ' '; } cout << '\n'; }

把 t 和算出来的 x 都打印出来，并排看，一眼就能发现问题。比如 t=23（10111），算出来 x=19（10011），可以看到 t 和 x 的差别只在第 2 位：t 第 2 位是 1，x 第 2 位是 0。这正好对应我们“x 是 t 把某一位置 0”的结论。如果打印出来的二进制差异不止一位，那说明程序里有 bug，或者你的公式推导方向有问题。

批量 check 也值得做。写一个循环，随机生成 10000 个奇数 t，对每个 t 用公式算 x，再用(x | (x+1)) == t验证。如果某个样例不满足，立刻就能定位是哪个 t 出了问题。实测下来，符合公式的解都能通过 check，这也进一步验证了推导的正确性。

6. 从这道题总结位运算数组题的通用打法

6.1 这类题的第一步永远是“观察单个位运算改了什么”

很多位运算的数组构造题，看起来千变万化，核心都逃不出一道工序：先抓住单个数值上的位运算效果。x | (x+1)是“找最低的 0 并翻成 1”，x & (x-1)是“把最低的 1 抹掉”，x ^ (x+1)是“获得一段连续 1”等等。把运算的位级效果写清楚，题目就成功了一半。

为什么这一步重要？因为位运算题的“反推”高度依赖你对正向着变换的理解。你如果只记住了某个公式，换一道题就抓瞎；但如果脑子里有“改哪一个位、保留哪些位”的画面，反推就会变成一件很直观的事。我在推导 3315 时，真正起作用的不是那个最终公式，而是“x 是 t 的某一位 1 被改成 0”这个认知。

6.2 构造中的“最小”往往由约束直接定死

构造题里经常出现“返回最小满足条件的数组”这类措辞。很多人第一反应是去枚举、比较、求极值，但位运算构造题通常不会真的让你在所有解里逐个比大小，而是通过位级约束把解空间压缩得很窄。

本题就是一个典型例子：所有合法解都能写成t - 2^k，k 的取值被限制在 0 到 m-1 范围内，一共也就 m 个候选。所谓的最小值，其实是“让 k 取到最大合法值”的自然结果。下次遇到类似的题，可以先尝试写出合法解的通项公式，再去考虑极值问题，通常比直接暴搜高效得多。

6.3 相近位运算套路：lowbit、拆位统计、枚举子集

顺着这道题可以联想到几个常用的位运算套路。第一是 lowbit，x & -x可以提取二进制里最低位的 1。本题虽然没直接用 lowbit，但 m 的求解与“连续 1 区间”相关，本质上也是对最低位区域的精细测量。第二是拆位统计，把数组里的每个数按二进制位拆开，逐位计算贡献，很多异或、与运算的题目都靠这个思路。第三是二进制枚举，当构造目标是“子集”或“组合”时，用位表示选择状态。

这些套路彼此并不孤立。比如本题需要读最低连续 1，你同样可以用一个循环配合右移去做；这跟前面提到的 m 计算是一类操作。打好这个基础，后面刷“按位与”“按位或”“异或前缀和”等题目会轻松很多。

6.4 一个小习惯：先列小表再写代码

最后分享一个我个人收益很大的习惯：遇到位运算题，不要急着打开 IDE 写代码，先在纸上列一张小表。把 0 到 15 或 0 到 31 的输入全部代进去，输出结果写成表格，盯着看几秒。

本题的核心规律，就是我从这张小表里看出来的。没有这张表，我可能会在公式推导上绕很久；有了这张表，所有候选解都摆在眼前，多解、偶数无解、最小解藏在减数最大的位置，全部一目了然。周赛的时候，时间很紧，但花五分钟列表、观察，往往比直接硬刚代码更快，也更稳。

这个习惯后来帮我解决了好几道位运算构造题。现在我可以很肯定地说：位运算题的答案，大多数时候不是“想”出来的，而是“看”出来的。