位运算构造最小数组：从 x|(x+1) 反推二进制连续1段规律

做这类构造题最怕一上来就盯着“怎么把数组填出来”结果被各种输出限制绕晕。LeetCode 3315《构造最小位运算数组 II》这道每日一题输入是一个数组输出也要求一个数组核心却不在数组本身而在每一位数字背后的二进制规律。我最早接触它的时候第一反应是枚举后来发现这题真正的考点是你能不能从x | (x1)这个操作的结果反推出最小的 x。这篇文章我会从题目拆解、位运算原理、代码实现、边界情况、对拍验证这几个角度完整讲一遍。无论是刚刷题的新手还是想快速复习位运算套路的老手都能在文章里找到可以直接抄走的东西。1. 题目到底在问什么先看懂x | (x1)的脾气1.1 一个数组输入、数组输出的构造题先明确题面给定一个非负整数数组nums对数组里的每一个数字nums[i]你需要构造出一个最小的非负整数x使得x | (x1) nums[i]成立。如果这样的x不存在对应位置返回-1。也就是说输出数组的每一位都是根据输入数组对应位的那个数字反推出来的。输入[1, 3, 4]输出可能是[0, 1, -1]因为0 | 1 11 | 2 3而找不到一个非负整数x能让x | (x1) 4。构造题有个特点它不像动态规划或图论那样需要状态转移而是需要你找到一种“生成规则”。这题的关键就是彻底看懂x | (x1)这个位运算操作到底对二进制的哪一位做了什么事情。1.2 拆解x | (x1)的底层行为先拿几个小数字做实验x 0二进制是0x 1 10 | 1 1x 1二进制是1x 1 2二进制是1001 | 10 11也就是3x 4二进制是100x 1 5二进制是101100 | 101 101也就是5x 7二进制是111x 1 8二进制是10000111 | 1000 1111也就是15观察二进制的人会立刻发现一件事x和x1是连续的整数它们除了最低那一段 1 会产生进位之外更高位基本保持不变。异或运算能把两个数的差异位标出来或运算则会把进位后新出现的 1 和原来低位的 1 全部保留。所以x | (x1)的结果本质上就是一个“给最低位连续的 1 段向右扩展一位”的操作。如果x 10111它的低位连续 1 段长度是 3那么x | (x1)得到的结果低位 1 段长度会变成 4也就是101111的一部分。1.3 用例子把规律钉死为了确保规律没有偏差我列一张对照表把x、x1、以及x | (x1)的关系摆在一起看xx 的二进制x1 的二进制x(x1)结果二进制001111110311410010151017111100015111191001101011101111101111001511111910011101002310111看到最后几行你应该有感觉了结果的低位连续 1 段长度永远比x的低位连续 1 段长度多 1。这是整个题目解题的钥匙。2. 从结果反推无解判定与答案构造公式2.1 为什么偶数一定无解先回答一个最直观的问题什么样的n一定不存在对应的x因为x和x1是连续的两个整数它们一奇一偶。奇数二进制最低位是 1偶数二进制最低位是 0。按位或之后最低位只要有任意一个 1结果就是 1。所以无论x是奇数还是偶数x | (x1)的结果最低位一定是 1。换句话说输入的n如果是个偶数最低位是 0那这个n根本就不可能是某个x | (x1)的结果。这种情况直接返回-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 位是 1x里第 1 位就必须变成 0更高位保持不变于是x 1001 9。再验证n 7低位连续 1 段长度是 3x的低位连续 1 段长度就是 2n里第 2 位是 1x里第 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 | (x1)的结果里低位连续 1 段的长度虽然是m但多出来的那个 1 不是靠“把n的第 m 位变成 1”得到的。n的第 m 位本身是 0而结果里的这个 1 来自进位原本在x的第 m 位那里是一个 0。真正发生变化的位置是x的“连续 1 段最高位”它会被x1的进位清成 0同时把下一个 0 位变成 1再进行或运算后低位原有的 1 全部保留。反推的时候只需要把n里这段连续 1 的最高位还原成 0其他位和n保持一样就行。所以核心只有一句话结果的低位连续 1 段长度比原数的低位连续 1 段长度多 1。反推就是把这个多余的 1 去掉。3. 代码实战从暴力枚举到 O(1) 构造3.1 用暴力验证公式的正确性在写最终代码之前我建议先写一个暴力版本方便对拍验证。对于一个给定的n直接从小到大枚举所有可能的x检查x | (x1)是否等于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: vectorint minBitwiseArray(vectorint nums) { vectorint 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 ansPython 里需要注意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二进制是111t依次是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 0ctz(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 一组特殊输入速查表我整理了一组测试用例建议提交前全部跑一遍输入 n低位连续 1 长度 m答案 x验证 x(x1)11001 12偶数-1无32112 34偶数-1无51445 573334 791889 91129910 11131121213 13154778 15233191920 23有了这个表大部分边界情况都能覆盖到。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(fmismatch: {n}, brute{brute(n)}, fast{fast(n)}) break else: print(all ok)这里没有用随机数据而是直接从 1 到 19999 全覆盖。因为范围不大暴力也跑得动。这样测试比纯随机更全面不会漏掉少数边界。5.2 用公式再反向验证除了和暴力对拍还可以做一层反向验证对公式算出来的每个x重新计算x | (x1)确认它等于输入的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 更有价值。