LeetCode 3315 构造最小位运算数组：位运算规律与公式推导

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 | (x1) 翻译成人话在推公式之前我习惯先拿一个实际的二进制数算一算搞清楚这个运算到底对 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 | (x1)可以理解成一句话在 x 的二进制表示中找到最低位的 0把它翻成 1更低的部分因为本来全是 1所以“顺手”保留。这个观察是整道题的命门后面的所有推导都从这里来。2. 从例子找规律三分钟推出答案公式2.1 先列一张“目标值-答案”的二进制小表我推导这类问题有个习惯先不空想直接把小范围内的数据全部算出来摆在面前找感觉。把 x 从 0 到 15 代入x | (x1)可以得到一张表xx 二进制x | (x1) 结果结果二进制001111311210311311711141005101510171116110711171111511118100091001910011110111010101110111110111511111211001311011311011511111411101511111511113111111这张表信息量很大。首先所有结果都是奇数没有一个偶数。其次同一个结果会对应多个 x比如 7 可以由 x3、5、6 三个数得到15 可以由 x7、11、13、14 得到。这说明了“最小”并不是摆设。第三结果的二进制形态非常有规律它总是一段从低位开始的连续 1有时候延伸到更高的位上。现在反过来看题目我们是以 target 为输入反推最小的 x。把 target 记为 t最低位连续 1 的个数记为 m。比如 t11m1t311m2t5101m1t7111m3。列一张“t 到求出来的最小 x”的表target t二进制最低连续 1 个数 m最小答案 x1110311215101147111339100118111011291311011121511114721101011202310111319偶数的情况先放一边显然都是 -1。奇数的规律已经按不住答案几乎都是t - 2^(m-1)。拿 23 验证23 的二进制是10111最低连续 1 是 3 个m323 - 2^2 19。19 的二进制是1001119 | 20 10011 | 10100 10111 23。成立。2.2 规律浮现答案 t - 2^(m-1)把这个规律写成公式就是ans t - 2^(m-1)其中 m 表示 t 的二进制表示里从最低位开始连续出现了多少个 1。举个例子t13二进制1101最低位连续 1 只有 1 个m1答案就是 13 - 1 12。t15二进制1111最低位连续 1 有 4 个m4答案是 15 - 8 7。所有奇数 t 都满足这个公式偶数一律无解。为什么偶数无解很简单看最低位。如果 x 最低位是 0那么 x1 最低位是 1或完之后最低位是 1如果 x 最低位是 1x1 会进位最低位变成 0但 x 自己最低位还是 1或完之后最低位仍然是 1。所以无论 x 是什么x | (x1)的结果最低位永远是 1也就是说结果永远是奇数。target 为偶数时直接返回 -1不需要再往下算。2.3 一个 target 可以对应多个 x最小解藏在公式里从 2.1 那张表已经能看到同一个 target 通常不只有一个来源。比如 target7x3、5、6 都能生成 7target15x7、11、13、14 都能生成 15。如果我们从大到小枚举 x第一个找到的常常是较大的解不是题目要的最小值。所以公式t - 2^(m-1)是不是真的对应最小解拿 7 验证7 的 m37 - 4 3确实是三个合法解里最小的那个。15 的 m415 - 8 7也是四个合法解里最小的。看起来公式给的正是最小值而不是随便一个合法解。为什么偏偏是它下一节用位级推导来解释。3. 位级推导为什么答案是 t - 2^(m-1)3.1 设 k 为 x 最低的 0 位x 到 t 只改了一位回到 1.3 的结论x | (x1)的作用是找到 x 二进制里最低位的 0记为第 k 位把它翻成 1低于 k 的位本来全是 1保持为 1高于 k 的位原样保留。这句话反过来理解如果x | (x1) 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不会出现借位。拿 t7 来验证m3k 可以取 0、1、2对应的 x 分别是 7-16、7-25、7-43。正是那张表里看到的三个合法解。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 为例二进制111m3答案 7 - 4 3。以 15 为例二进制1111m4答案 15 - 8 7。这种情况下“第 m 位”其实已经超过 t 的有效二进制长度可以认为更高一位天然是 0正好符合条件。所以公式不需要额外加特判。整个推导最终浓缩成三步判断是否为偶数如果是奇数数出最低连续 1 的个数 m返回t - 2^(m-1)。代码量非常小但每一步都有位级逻辑撑着。4. 落地成代码三种语言的完整实现4.1 C 完整解法与注释推导完成之后写代码就是照搬公式。C 版本我写得比较啰嗦但每一步都对应刚才的分析class Solution { public: vectorint minBitwiseArray(vectorint nums) { int n nums.size(); vectorint 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做左移再强转回 intclass 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 的写法用 tm 来探测 while (((t m) 1) 1) { m; } ans[i] (int) (t - (1L (m - 1))); } return ans; } }这里我没有复制 cur而是通过t m来探测第 m 位是否为 1。这个写法更安全也更紧凑。m 从 0 开始第 0 位是 1m 变为 1再探测第 1 位如果还是 1m 继续加直到遇到 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 ansPython 里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}。这里面包含了偶数无解、m1、m2、m3、m4 的各种情况。更推荐的做法是写一个随机测试随机生成若干个奇数 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 早就不是原始值了。比如 t13右移第一次13 1 6第二次6 1 0循环结束此时 t6答案变成了 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 变成 0m 可能很大对于奇数 tm 一开始就是 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 级别最坏情况下要试很多次。第二是方向反了从大往小找找到的第一个满足条件的解其实是最大的合法解而题目要的是最小解。以 t7 为例从 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 都打印出来并排看一眼就能发现问题。比如 t2310111算出来 x1910011可以看到 t 和 x 的差别只在第 2 位t 第 2 位是 1x 第 2 位是 0。这正好对应我们“x 是 t 把某一位置 0”的结论。如果打印出来的二进制差异不止一位那说明程序里有 bug或者你的公式推导方向有问题。批量 check 也值得做。写一个循环随机生成 10000 个奇数 t对每个 t 用公式算 x再用(x | (x1)) t验证。如果某个样例不满足立刻就能定位是哪个 t 出了问题。实测下来符合公式的解都能通过 check这也进一步验证了推导的正确性。6. 从这道题总结位运算数组题的通用打法6.1 这类题的第一步永远是“观察单个位运算改了什么”很多位运算的数组构造题看起来千变万化核心都逃不出一道工序先抓住单个数值上的位运算效果。x | (x1)是“找最低的 0 并翻成 1”x (x-1)是“把最低的 1 抹掉”x ^ (x1)是“获得一段连续 1”等等。把运算的位级效果写清楚题目就成功了一半。为什么这一步重要因为位运算题的“反推”高度依赖你对正向着变换的理解。你如果只记住了某个公式换一道题就抓瞎但如果脑子里有“改哪一个位、保留哪些位”的画面反推就会变成一件很直观的事。我在推导 3315 时真正起作用的不是那个最终公式而是“x 是 t 的某一位 1 被改成 0”这个认知。6.2 构造中的“最小”往往由约束直接定死构造题里经常出现“返回最小满足条件的数组”这类措辞。很多人第一反应是去枚举、比较、求极值但位运算构造题通常不会真的让你在所有解里逐个比大小而是通过位级约束把解空间压缩得很窄。本题就是一个典型例子所有合法解都能写成t - 2^kk 的取值被限制在 0 到 m-1 范围内一共也就 m 个候选。所谓的最小值其实是“让 k 取到最大合法值”的自然结果。下次遇到类似的题可以先尝试写出合法解的通项公式再去考虑极值问题通常比直接暴搜高效得多。6.3 相近位运算套路lowbit、拆位统计、枚举子集顺着这道题可以联想到几个常用的位运算套路。第一是 lowbitx -x可以提取二进制里最低位的 1。本题虽然没直接用 lowbit但 m 的求解与“连续 1 区间”相关本质上也是对最低位区域的精细测量。第二是拆位统计把数组里的每个数按二进制位拆开逐位计算贡献很多异或、与运算的题目都靠这个思路。第三是二进制枚举当构造目标是“子集”或“组合”时用位表示选择状态。这些套路彼此并不孤立。比如本题需要读最低连续 1你同样可以用一个循环配合右移去做这跟前面提到的 m 计算是一类操作。打好这个基础后面刷“按位与”“按位或”“异或前缀和”等题目会轻松很多。6.4 一个小习惯先列小表再写代码最后分享一个我个人收益很大的习惯遇到位运算题不要急着打开 IDE 写代码先在纸上列一张小表。把 0 到 15 或 0 到 31 的输入全部代进去输出结果写成表格盯着看几秒。本题的核心规律就是我从这张小表里看出来的。没有这张表我可能会在公式推导上绕很久有了这张表所有候选解都摆在眼前多解、偶数无解、最小解藏在减数最大的位置全部一目了然。周赛的时候时间很紧但花五分钟列表、观察往往比直接硬刚代码更快也更稳。这个习惯后来帮我解决了好几道位运算构造题。现在我可以很肯定地说位运算题的答案大多数时候不是“想”出来的而是“看”出来的。