今天刷到 LeetCode 每日一题 3315题目全称是“构造最小位运算数组 II”。只看名字会觉得又是一道模拟构造题读完题面才发现它其实是给你一堆目标值让你逆推一个满足位运算公式的最小整数。核心公式很简单x | (x 1) nums[i]。如果理解到位运算的进位这道题能在一分钟内写出核心代码如果只会枚举碰到II这个加强版就很容易超时。下面我从题目还原开始把推导过程、完整代码和提交时踩过的坑一起说清楚适合想用位运算思维刷数组构造题的朋友直接参考。1. 先把题目读明白正向的一行公式逆向的一个数组1.1 输入输出长什么样题目会给你一个整数数组nums要求返回等长的数组ans。对于每一个位置ians[i]要满足ans[i] | (ans[i] 1) nums[i]而且这个ans[i]必须是所有满足条件的整数里最小的那个。如果不存在这样的整数就填-1。举个例子输入nums [3, 5, 7, 11]返回[1, 4, 3, 9]。验证一下1 | 2 34 | 5 53 | 4 79 | 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)列出来规律其实非常明显xx 的二进制f(x)00111321033117410055101761107711115这张表透露了两件事第一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 | 2410111 | 11000 11111。对比x和f(x)的二进制最低的四位本来就都是 1OR 之后还是 1原来第一个 0 的位置在第四位OR 之后变成了 1。换句话说f(x)做的事情就是把x二进制里从右往左数第一个 0 改成 1。这个描述非常重要。因为x 1会改变一串低位但 OR 操作把那些原本为 1 的低位又“保留”了下来最后只剩最低的那个 0 位被真正翻转。2.2 结论一结果永远是奇数既然f(x)会把最低位的那个 0 变成 1那么结果的第 0 位一定是 1不管x是奇数还是偶数。如果x是奇数最低位本来就是 1x 1让最低位变 0OR 之后又变回 1。如果x是偶数最低位本来是 0x 1让最低位变 1OR 之后就是 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二进制是1011c 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二进制111c 3。合法的p可以取 0、1、2对应三个合法的xp2^px 7 - 2^p验证 f(x)0166 | 7 71255 | 6 72433 | 4 7三个x都满足条件但最小的那个对应最大的p。因为减去的2^p越大剩下的数就越小。3.2 最小答案清掉连续 1 区间里最高位的那一位所以解法很明确对奇数Y找到c Y二进制结尾连续 1 的个数然后让x Y ^ (1 (c - 1))也就是把Y的倒数第c位从 1 变成 0。再拿Y 23验证c 31 (c - 1) 423 ^ 4 19。19的二进制是1001119 | 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 11Y 1 12low 4low 1 2ans 11 ^ 2 9Y 21Y 1 22low 2low 1 1ans 21 ^ 1 20。3.4 边界情况Y 1 和全 1Y 1的时候c 1low 2ans 1 ^ 1 0。0 | 1 1没问题。如果题面里写的是“正整数x”那么 0 不算这种情况需要单独返回-1但 LeetCode 这道题按非负整数处理答案是 0。Y 7、15、31这类全 1 的数c等于它的二进制位数答案分别是3、7、15。这个边界很容易验证代码写对了就能对得上。4. 完整代码从原理落到提交4.1 先写一个最直观的版本为了保险可以先写一个数连续 1 的版本逻辑和推导完全一一对应。Pythonfrom 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: vectorint minBitwiseArray(vectorint nums) { vectorint 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 1num 1时循环版本里c 11 (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 1Java 用(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)这几个操作各有什么作用以及它们和加一减一的关系。把这几个基础操作混熟之后再看这类“给结果逆推运算”的题就不会觉得无从下手了。