LeetCode 3315 位运算题解：构造最小位运算数组 II 的逆推方法

今天刷到 LeetCode 每日一题 3315，题目全称是“构造最小位运算数组 II”。只看名字会觉得又是一道模拟构造题，读完题面才发现，它其实是给你一堆目标值，让你逆推一个满足位运算公式的最小整数。核心公式很简单：x | (x + 1) == nums[i]。如果理解到位运算的进位，这道题能在一分钟内写出核心代码；如果只会枚举，碰到II这个加强版就很容易超时。下面我从题目还原开始，把推导过程、完整代码和提交时踩过的坑一起说清楚，适合想用位运算思维刷数组构造题的朋友直接参考。

1. 先把题目读明白：正向的一行公式，逆向的一个数组

1.1 输入输出长什么样

题目会给你一个整数数组nums，要求返回等长的数组ans。对于每一个位置i，ans[i]要满足：

ans[i] | (ans[i] + 1) == nums[i]

而且这个ans[i]必须是所有满足条件的整数里最小的那个。如果不存在这样的整数，就填-1。

举个例子，输入nums = [3, 5, 7, 11]，返回[1, 4, 3, 9]。验证一下：1 | 2 = 3，4 | 5 = 5，3 | 4 = 7，9 | 10 = 11。从这里就能看出，题目里的“最小”不是随便写的，比如6 | 7也等于 7，但 6 不是最小的答案，因为 3 同样能满足。

1.2 为什么说这是逆推题

正向的x | (x + 1)很好算，但题目给的是结果，要反推出x。更麻烦的是，同一个结果可能对应好几个x。比如x = 3、x = 5、x = 6、x = 7代入x | (x + 1)结果都是 7，必须额外比较哪个最小。

如果只有一两个数，暴力从 0 枚举到nums[i]也不是不行。但既然题目叫“构造最小位运算数组 II”，说明它是上一题I的加强版，nums[i]的规模通常会大到没法枚举。这时候就需要从二进制本身找规律，而不是把每个数试一遍。

1.3 先看一张小表

把 0 到 7 的f(x) = x | (x + 1)列出来，规律其实非常明显：

这张表透露了两件事：第一，f(x)永远都是奇数，所以偶数目标值可以直接判死；第二，f(x)和x之间往往只差一个二进制位。这两点就是整个题解的入口。

2. 核心观察：x | (x + 1)到底改了什么

2.1 从加法的连续进位说起

要理解x | (x + 1)，先看x + 1在二进制里会发生什么。

比如x = 23，二进制是10111。加 1 的时候，最低位是 1，会产生进位；第二位也是 1，继续进位；第三位还是 1，继续进位；直到第四位原本是 0，进位到这里变成 1，进位才停住。所以23 + 1 = 24，也就是11000。

再看23 | 24：10111 | 11000 = 11111。对比x和f(x)的二进制，最低的四位本来就都是 1，OR 之后还是 1；原来第一个 0 的位置在第四位，OR 之后变成了 1。换句话说，f(x)做的事情，就是把x二进制里从右往左数第一个 0 改成 1。

这个描述非常重要。因为x + 1会改变一串低位，但 OR 操作把那些原本为 1 的低位又“保留”了下来，最后只剩最低的那个 0 位被真正翻转。

2.2 结论一：结果永远是奇数

既然f(x)会把最低位的那个 0 变成 1，那么结果的第 0 位一定是 1，不管x是奇数还是偶数。

• 如果x是奇数，最低位本来就是 1，x + 1让最低位变 0，OR 之后又变回 1。
• 如果x是偶数，最低位本来是 0，x + 1让最低位变 1，OR 之后就是 1。

所以f(x)不可能是偶数。拿到一个nums[i]，先看它是不是偶数，是偶数直接填-1，这一步过滤掉了一半的数据。

2.3 结论二：命中的是同一个 0

更严格地说，设p是x二进制里从右往左第一个 0 的位置，那么f(x)和x的区别就只在第p位，其余位完全相同。于是有：

f(x) = x + 2^p

这是个很强的等式。正向看，一旦确定p，结果就确定了；逆向看，给定目标值Y = nums[i]，x必须是Y减去某个2^p得到的数。现在的任务就变成了：这个p到底可以取哪些值？

3. 反推答案：数目标值结尾连续 1 的个数

3.1 目标值的连续 1 后缀决定了所有合法 p

假设目标值Y是奇数，它的二进制最低位一定是 1。从低位往高位数，连续出现的 1 的个数记作c。

例如Y = 23，二进制是10111，结尾有 3 个连续的 1，所以c = 3。Y = 11，二进制是1011，c = 2。Y = 21，二进制是10101，结尾只有一个 1，所以c = 1。

之前说过，构造出来的x = Y - 2^p，而且x的最低p位必须是 1、第p位必须是 0。这意味着Y从最低位开始的前p + 1位都必须是 1，所以p只能落在 0 到c - 1这个范围内。

为什么p不能大于等于c？因为目标值Y的第c位是 0，如果清掉更高的一位，最低位的 0 依然在第c位，x + 1的进位根本不会传到p。换句话说，真正决定结果的是Y结尾这段连续 1，不是靠上的任意 1。

举个例子，Y = 7，二进制111，c = 3。合法的p可以取 0、1、2，对应三个合法的x：

三个x都满足条件，但最小的那个对应最大的p。因为减去的2^p越大，剩下的数就越小。

3.2 最小答案：清掉连续 1 区间里最高位的那一位

所以解法很明确：对奇数Y，找到c = Y二进制结尾连续 1 的个数，然后让x = Y ^ (1 << (c - 1))，也就是把Y的倒数第c位从 1 变成 0。

再拿Y = 23验证：c = 3，1 << (c - 1) = 4，23 ^ 4 = 19。19的二进制是10011，19 | 20 = 10011 | 10100 = 10111 = 23。而且 19 确实比另一个合法答案 21 要小。

3.3 用 lowbit 一步拿到 c-1 位

问题来了：计算c需要循环数 1，能不能用位运算直接算？能。

如果Y结尾有c个连续的 1，那么Y + 1结尾刚好有c个连续的 0，并且第c位变成 1。也就是说，Y + 1的最低位 1 对应的权值是2^c。用 lowbit 公式：

low = (Y + 1) & -(Y + 1)

得到的是2^c。而我们想清掉的位是第c - 1位，权值是2^(c - 1)，正好是low >> 1。所以最终答案一行搞定：

ans = Y ^ (low >> 1)

看两个例子：Y = 11，Y + 1 = 12，low = 4，low >> 1 = 2，ans = 11 ^ 2 = 9；Y = 21，Y + 1 = 22，low = 2，low >> 1 = 1，ans = 21 ^ 1 = 20。

3.4 边界情况：Y = 1 和全 1

Y = 1的时候，c = 1，low = 2，ans = 1 ^ 1 = 0。0 | 1 = 1，没问题。如果题面里写的是“正整数x”，那么 0 不算，这种情况需要单独返回-1；但 LeetCode 这道题按非负整数处理，答案是 0。

Y = 7、15、31这类全 1 的数，c等于它的二进制位数，答案分别是3、7、15。这个边界很容易验证，代码写对了就能对得上。

4. 完整代码：从原理落到提交

4.1 先写一个最直观的版本

为了保险，可以先写一个数连续 1 的版本，逻辑和推导完全一一对应。Python：

from typing import List class Solution: def minBitwiseArray(self, nums: List[int]) -> List[int]: ans = [] for num in nums: if num % 2 == 0: ans.append(-1) continue # 数 num 二进制结尾连续 1 的个数 c = 0 while (num >> c) & 1: c += 1 # 把从右往左第 c 位（权值 1 << (c - 1)）清 0 ans.append(num ^ (1 << (c - 1))) return ans

这个版本不需要任何奇技淫巧，while循环最多跑 30 次，通常已经能通过。但它还不是最优雅的。

4.2 用 lowbit 精简掉循环

既然c = ctz(num + 1)，那就不需要 while。Python 可以写成：

class Solution: def minBitwiseArray(self, nums: List[int]) -> List[int]: ans = [] for num in nums: if num % 2 == 0: ans.append(-1) continue low = (num + 1) & -(num + 1) # 2 的 c 次方 ans.append(num ^ (low >> 1)) return ans

(num + 1) & -(num + 1)就是 lowbit 的经典写法，取的是num + 1最低位 1 对应的权值。low >> 1自动等价于1 << (c - 1)，代码短，思路也清晰。

C++ 版本：

class Solution { public: vector<int> minBitwiseArray(vector<int>& nums) { vector<int> ans; for (int num : nums) { if (num % 2 == 0) { ans.push_back(-1); continue; } long long t = num + 1LL; long long low = t & -t; ans.push_back(num ^ (int)(low >> 1)); } return ans; } };

Java 版本：

class Solution { public int[] minBitwiseArray(int[] nums) { int[] ans = new int[nums.length]; for (int i = 0; i < nums.length; i++) { int num = nums[i]; if ((num & 1) == 0) { ans[i] = -1; } else { long t = (long) num + 1; long low = t & -t; ans[i] = num ^ (int) (low >> 1); } } return ans; } }

这三个版本核心逻辑完全一样，差异只在要不要担心 int 溢出。用num - (low >> 1)也能得到同样的结果，因为要清掉的那一位一定是 1；不过用异或更能体现“只翻转指定位”的位运算初衷。

4.3 复杂度分析

每个元素只做常数次加减、按位与、按位异或，所以时间复杂度是O(n)。空间方面只用了输出数组本身，额外空间是O(1)。如果使用 while 数连续 1，也不会改变复杂度的量级，因为num的二进制位数是有限的，最多算 30 或 31 次。

5. 我提交时踩过的坑

5.1 把 c 数成了 0

第一次我顺手用了__builtin_ctz(num)或者 Python 里的(num & -num)，结果对num = 11这种奇数怎么算都不对。原因很简单：ctz是数尾随 0，不是尾随 1。奇数最低位是 1，尾随 0 当然是 0。正确做法是数num + 1的尾随 0，也就是ctz(num + 1)。从原理上记：连续 1 的个数，正好等于加一之后连续 0 的个数。

5.2 以为答案是 num - 1

看到6 | 7 = 7、10 | 11 = 11，很容易有人直接写num - 1。对num = 11确实能算出 10，但 10 不是最小答案，9 才是。问题要求的是“最小”，不是“随便一个”。所以只要目标值结尾连续 1 的长度超过 1，就必须清掉最靠左的那个 1，而不是最低位那个 1。

5.3 忘了处理 num = 1

num = 1时，循环版本里c = 1，1 << (c - 1) = 1，答案是 0，看起来没什么特别的。但如果你在代码里最开始判断if num == 1: return -1，反而会错。要不要特判取决于题面定义的是非负整数还是正整数。我刷到的是非负整数，所以答案是 0。大家在别的平台遇到类似题时，先看题面里有没有“positive”这个词。

5.4 int 溢出

C++ 和 Java 里，num + 1在num = INT_MAX时会溢出。虽然 LeetCode 的常规数据范围一般到不了这么极端，但写位运算题养成长整型习惯没有坏处。C++ 用1LL * num + 1，Java 用(long) num + 1，就能完全避开这种隐性 bug。

6. 这道题背后的位运算套路值得记下来

6.1 lowbit(n + 1) 就是“连续 1 长度”的开关

n的二进制结尾连续 1 的个数，可以通过n + 1的 lowbit 直接算出权值。这个技巧在这题里是核心，在其他题里也经常出现。比如判断一个数是不是2^k - 1，可以看n + 1是不是 2 的幂；处理区间连续 1 的问题，也可以用类似思路把问题压缩到最低位附近。

遇到形如x | (x + 1)、x & (x + 1)这种组合，我现在的第一反应不是展开表达式，而是想“加 1 之后进位到哪一位停住”。位运算和加减法混在一起时，进位过程往往比结果本身更值得分析。

6.2 小表比公式更快的场景

这题我一开始也卡了几分钟，后来把x = 0到7的x | (x + 1)列了一张表，规律立刻清楚了。刷每日一题卡住的时候，先别急着翻题解，花两分钟列一张小表，把 0 到 15 的结果写出来，很多位运算规律都是肉眼可见的。这个习惯帮我省下过不少看题解的时间。

6.3 如果还想继续练

想巩固这道题相关的位运算直觉，可以顺手把“尾随 0/1”的计数再练一遍：ctz、clz、lowbit、n & (n - 1)这几个操作各有什么作用，以及它们和加一减一的关系。把这几个基础操作混熟之后，再看这类“给结果逆推运算”的题，就不会觉得无从下手了。