反向构造最小位运算数组的位运算规律)
LeetCode 每日一题刷到 3315 的时候我盯着这个“构造最小位运算数组 II”看了很久。题目背景很简单给你一个数组 nums要构造另一个数组 ans让每个位置都满足 ans[i] | (ans[i] 1) nums[i]而且 ans[i] 要尽可能小找不到就填 -1。看起来就是一个普通的位运算、数组构造题但我第一天提交的代码是用 0 到 nums[i] 逐个试的暴力枚举结果在数据范围更大的 II 版里直接超时。后来把式子拆开才发现整道题的本质只有一句话x | (x 1)只是把 x 二进制里最低的那个 0 变成了 1。如果你正在刷位运算专题或者被这类“反向构造”题卡住这篇内容应该能帮你省下不少时间。1. 题面很短坑很长这道构造题到底在问什么1.1 题意还原每个位置是独立的小问题题目名字带个 II说明多半是第一道题的进阶版。第一版数据范围通常比较小允许 O(n * v) 这样的暴力II 版会把 n 或 nums[i] 的范围放大逼着你总结出位运算层面的规律。你要构造的是一个和 nums 等长的数组每个元素之间完全独立所以问题可以拆成单点问题给定一个数 y找出最小的 x使得x | (x 1) y如果这样的 x 不存在输出 -1。我一开始的想法很简单既然 x 不会太大那就从小到大枚举 x找到第一个满足条件的就是最小解。可是这里有个隐藏问题我们根本不知道 x 的上界。试了几个例子比如 y 7 的时候 x 3 就能满足但 y 15 的时候答案变成 7换句话说答案可以接近 y / 2也可以很小枚举的终止条件不好写而且 [0, y] 的范围在数据大时完全不可行。另外一个容易忽视的细节是题目要求的是“最小位运算数组”不是随便找一组可行解。比如 y 7x 6 也能让6 | 7 7但最小解是 x 3因为3 | 4 7。所以只判断“能不能构造”不够还要在所有可行解里选出最小的那个。这种“构造 最优化”的组合往往是位运算题里最花时间的部分。1.2 先别急着写代码把 f(x) 拆开这种题最忌讳上来就写循环。我们应该先回答一个更基础的问题x | (x 1)这个操作在二进制层面到底做了什么看 x 1 的进位过程从最低位开始遇到连续的 1 就一直进位直到碰见第一个 0把它变成 1再往前的更高位完全不动。所以关键就在那个“最低的 0”。如果把这一步想清楚题目就从“枚举 判断”变成了“定位 回改”难度完全不同。2. f(x) x | (x 1) 的位级真相进位的落点一目了然2.1 先列一个表观察规律我习惯拿到位运算题先写个小表用二进制直接看变化x 二进制x 1 二进制f(x) 二进制被改变的位0100 (4)0101 (5)0101 (5)bit0 从 0 变 10110 (6)0111 (7)0111 (7)bit1 从 0 变 11011 (11)1100 (12)1111 (15)bit2 从 0 变 11101 (13)1110 (14)1111 (15)bit1 从 0 变 1规律非常明显f(x) 只是把 x 中从低位往高处数第一个出现的 0 改写为 1其它位一律不动。用公式写设 t 是最低 0 位的位置则f(x) x | (1 t)为什么不是把整串 1 都改掉因为最低 0 的右侧本来就是 1x 1 虽然会把这一串 1 清成 0但接着做或运算时x 原本的 1 又全部补了回来。最终只有那个 0 位发生变化。2.2 x 1 的进位细节再看一个例子x 0b1011123从低位开始 bit0、bit1、bit2 都是 1bit3 是第一个 0。x 1 0b1100024进位把低三位清成 0把 bit3 变成 1。这时候 x | (x 1) 0b10111 | 0b11000 0b1111131相当于是让 bit3 从 0 变成了 1低三位依然保持原来的 1。这个观察的威力在于它把“求一个函数值”变成“找二进制里的一个特征位置”。而反向构造就成了在目标 y 里找出刚才那个被改过的 0 位。2.3 立刻得到一个硬性结论偶数无解因为 f(x) 不管最低 0 位出现在哪里最低位 bit0 要么本来已经是 1要么由 0 变 1。所以 f(x) 永远是奇数。反过来如果 nums[i] 是偶数直接不可能有解答案就是 -1。这个结论看起来简单但代码里如果漏掉后面用 __builtin_ctz 很容易出错。想一下nums[i] 如果是偶数说明它的最低位是 0你拿它去套“连续尾 1”的公式会得到 r 0然后出现 1 (r - 1) 这种右移负数的未定义行为。所以偶数判断必须放在最前面。3. 反向构造的最小值证明为什么答案是 y 减掉 2^(r-1)3.1 用连续尾 1 的长度定位候选位置既然 y 必须是奇数我们只看奇数。设 r 是 y 从 bit0 开始第一个 0 的位置。因为 y 是奇数bit0 1所以至少 r 1从 bit0 到 bit(r - 1) 全是 1bit r 是 0。换句话说r 就是 y 二进制末尾连续 1 的个数。现在假设存在一个 x让 f(x) y。设 x 里被改的那个 0 位是 t。由于 t 是 x 的最低 0 位x 的 bit0 到 bit(t-1) 一定全是 1f(x) 后bit t 变成 1。因此 y 的 bit0 到 bit t 也全部是 1。如果 t 已经大于等于 r那么 y 的 bit r 会是 1但按定义 y 的 bit r 是 0矛盾。于是 t 的取值范围被死死限制在0 t r - 1这是一个关键收敛解的数量最多只有 r 个而不是无穷多个。例如 y 23二进制是 10111连续尾 1 长度 r 3那么 t 只能取 0、1、2。3.2 每个候选解长什么样对每一个合法的 t反向操作就是把 y 的 bit t 重新改回 0其它位保持不动。写成x_t y ^ (1 t)由于 y 在 bit t 处本来就是 1异或清零等价于减去 2^t。这些 x_t 全部合法吗验证一下x_t 的 bit0 到 bit(t-1) 仍然是 1bit t 是 0所以 x_t 的最低 0 位确实就是 t。对它执行 fbit t 变 1其余位不变恰好回到 y。拿 y 23 举例子三个候选分别是t 0x 22二进制 1011022 | 23 23t 1x 21二进制 1010121 | 22 23t 2x 19二进制 1001119 | 20 23三个都成立这时候问题就变成了选哪一个能让 x 最小。3.3 最小解的选择比较候选解的本质是在问把 y 的第几位清 0减掉的值最大因为 y 在 bit t 是 1所以x_t y - 2^t显然 t 越大减掉的 2^t 越大结果越小。因此最小解取 t r - 1也就是ans y - 2^(r - 1)把这个公式带回刚才的例子23 - 4 19确实是三个候选里的最小。再多试几个y 7二进制 111r 3ans 7 - 4 33 | 4 7y 13二进制 1101r 1ans 13 - 1 1212 | 13 13y 15二进制 1111r 4ans 15 - 8 77 | 8 15公式全部成立。3.4 这里最容易被绕晕的一点我踩过的坑是不要试图去找 y 的“最低 0 位”然后把它改成 1。我们是要在 y 的连续尾 1 里选一个位置改回 0不是改 y 的第一个 0。连续尾 1 长度 r 的求法有很多最方便的是借助 y 1因为 y 1 会把末尾的连续 1 全变成 0再把第一个 0 变成 1所以 y 1 的二进制末尾 0 个数恰好等于 r。例如 y 23y 1 24二进制 11000末尾 3 个 0r 3。在 C 里就是__builtin_ctz(y 1)在 Python 里用 lowbit 的位数。4. 三种实现与边界处理从暴力枚举到一行公式4.1 最直白的实现逐位找 r如果对内置函数不熟循环找 r 也完全够用vectorint constructArray(vectorint nums) { int n nums.size(); vectorint ans(n); for (int i 0; i n; i) { long long v nums[i]; if ((v 1LL) 0) { ans[i] -1; continue; } int r 0; while ((v r) 1LL) r; ans[i] (int)(v - (1LL (r - 1))); } return ans; }复杂度是 O(n * 31)对 LeetCode 的数据足够。用 long long 是为了防止移位越界和 INT_MAX 加 1 的问题。这里的 while 循环每轮最多跑 31 次因为 int 范围的正整数二进制位就这么多。4.2 用 __builtin_ctz 压缩到 O(n)vectorint constructArray(vectorint nums) { int n nums.size(); vectorint ans(n); for (int i 0; i n; i) { unsigned int v (unsigned int)nums[i]; if ((v 1u) 0) { ans[i] -1; continue; } int r __builtin_ctz(v 1u); ans[i] (int)(v - (1u (r - 1))); } return ans; }注意__builtin_ctz的参数是 unsigned int且参数为 0 时行为未定义。这里由于只处理奇数v 1 至少是 2不会为 0而转成 unsigned 之后INT_MAX 1 也定义良好。另一个容易错的地方是1 (r - 1)当 r - 1 达到 31 时int 的1 31是未定义行为所以要么用 unsigned要么直接用1LL ...。4.3 Python 版本甚至可以写成一行Python 没有直接的 ctz不过 lowbit 可以模拟(v 1) -(v 1)得到的是 v 1 的最低 1 位对应的值它的 2 的幂指数就是 r。而1 (r - 1)恰好等于 lowbit(v 1) 1。所以核心逻辑可以写成if v 1: ans[i] v - (((v 1) -(v 1)) 1) else: ans[i] -1验证 v 2324 -24 8右移一位得 423 - 4 19。验证 v 78 -8 8右移一位得 47 - 4 3。核心构造部分的代码就这一行。4.4 边界情况汇总输入情况处理方式原因nums[i] 为偶数答案 -1f(x) 一定是奇数nums[i] 0答案 -10 是偶数直接进入 -1 分支nums[i] 为奇数但很大比如 INT_MAX答案仍合法用 unsigned 或 long long 避免 1 溢出nums[i] 二进制全 1如 15公式照常工作连续尾 1 的范围就是整个二进制长度第一个 0 在更高位特别是最后一种情况比如 y 15二进制是 1111没有“中间”的 0 位但公式依然能算出 7。不要因为看到“找一个 0 位”就下意识认为全 1 的输入会出错。5. 把结论交给打表验证顺便聊聊这类题的迁移5.1 全量小数据暴力对照写公式最怕某个地方想当然所以我每次都会再补一段暴力验证。对 v 从 1 到 2000暴力枚举 x 从 0 到 v找最小的满足x | (x 1) v的数和公式结果比对。抽样结果v公式答案暴力最小 x结果100一致544一致733一致988一致1199一致131212一致1577一致171616一致231919一致如果你的代码跑完这一轮还能全过基本可以放心提交。注意暴力枚举里 x 0 也别忘了它和 x 1 这样的小值经常是答案。5.2 这套思路可以平移到哪些题位运算题里经常出现“某个操作只影响一个特征位”的形式比如x (x - 1)是去掉最低的 1x | (x 1)是填掉最低的 0x -x是提取最低的 1遇到这类操作第一步都是先明确它动了哪一位第二步反向构造就会简单很多。树状数组里的 lowbit、一些状态压缩题目里的末尾连续 1 统计本质上都在用同一个 ctz / trailing ones 概念。5.3 刷题时的个人习惯我现在的固定套路是拿到这种“构造最小 XX”的题先用小数据打表猜规律再回到二进制里验证最后才看题解。这道 3315 是我近期遇到的最典型一题题面短推导过程也不长但能把“枚举找答案”和“找规律直接算答案”两种思路对比得很清楚。如果你最近刷 BFS 刷得多偶尔换换位运算构造题反而会觉得思路清爽不少。不过这类题的共同原则是别急着套模板先把操作的本质写出来。最后再分享一个小技巧比赛里如果时间紧不必先写严格的数学证明。你可以先写暴力观察是不是只有 -1 和y - 2^(r - 1)两种输出确认之后再单独写一版 O(n) 的公式实现最后用暴力版本做差分对照。我提交前把 1 到 100000 的暴力结果和公式结果全部对了一遍确认没有边界漏网才敢上 O(n) 版本。这个流程虽然多写了十几行代码但能省下很多 Debug 时间。这就是我处理 3315 的全部经验希望对你有用。
LeetCode 3315：x|(x+1)反向构造最小位运算数组的位运算规律
LeetCode 每日一题刷到 3315 的时候我盯着这个“构造最小位运算数组 II”看了很久。题目背景很简单给你一个数组 nums要构造另一个数组 ans让每个位置都满足 ans[i] | (ans[i] 1) nums[i]而且 ans[i] 要尽可能小找不到就填 -1。看起来就是一个普通的位运算、数组构造题但我第一天提交的代码是用 0 到 nums[i] 逐个试的暴力枚举结果在数据范围更大的 II 版里直接超时。后来把式子拆开才发现整道题的本质只有一句话x | (x 1)只是把 x 二进制里最低的那个 0 变成了 1。如果你正在刷位运算专题或者被这类“反向构造”题卡住这篇内容应该能帮你省下不少时间。1. 题面很短坑很长这道构造题到底在问什么1.1 题意还原每个位置是独立的小问题题目名字带个 II说明多半是第一道题的进阶版。第一版数据范围通常比较小允许 O(n * v) 这样的暴力II 版会把 n 或 nums[i] 的范围放大逼着你总结出位运算层面的规律。你要构造的是一个和 nums 等长的数组每个元素之间完全独立所以问题可以拆成单点问题给定一个数 y找出最小的 x使得x | (x 1) y如果这样的 x 不存在输出 -1。我一开始的想法很简单既然 x 不会太大那就从小到大枚举 x找到第一个满足条件的就是最小解。可是这里有个隐藏问题我们根本不知道 x 的上界。试了几个例子比如 y 7 的时候 x 3 就能满足但 y 15 的时候答案变成 7换句话说答案可以接近 y / 2也可以很小枚举的终止条件不好写而且 [0, y] 的范围在数据大时完全不可行。另外一个容易忽视的细节是题目要求的是“最小位运算数组”不是随便找一组可行解。比如 y 7x 6 也能让6 | 7 7但最小解是 x 3因为3 | 4 7。所以只判断“能不能构造”不够还要在所有可行解里选出最小的那个。这种“构造 最优化”的组合往往是位运算题里最花时间的部分。1.2 先别急着写代码把 f(x) 拆开这种题最忌讳上来就写循环。我们应该先回答一个更基础的问题x | (x 1)这个操作在二进制层面到底做了什么看 x 1 的进位过程从最低位开始遇到连续的 1 就一直进位直到碰见第一个 0把它变成 1再往前的更高位完全不动。所以关键就在那个“最低的 0”。如果把这一步想清楚题目就从“枚举 判断”变成了“定位 回改”难度完全不同。2. f(x) x | (x 1) 的位级真相进位的落点一目了然2.1 先列一个表观察规律我习惯拿到位运算题先写个小表用二进制直接看变化x 二进制x 1 二进制f(x) 二进制被改变的位0100 (4)0101 (5)0101 (5)bit0 从 0 变 10110 (6)0111 (7)0111 (7)bit1 从 0 变 11011 (11)1100 (12)1111 (15)bit2 从 0 变 11101 (13)1110 (14)1111 (15)bit1 从 0 变 1规律非常明显f(x) 只是把 x 中从低位往高处数第一个出现的 0 改写为 1其它位一律不动。用公式写设 t 是最低 0 位的位置则f(x) x | (1 t)为什么不是把整串 1 都改掉因为最低 0 的右侧本来就是 1x 1 虽然会把这一串 1 清成 0但接着做或运算时x 原本的 1 又全部补了回来。最终只有那个 0 位发生变化。2.2 x 1 的进位细节再看一个例子x 0b1011123从低位开始 bit0、bit1、bit2 都是 1bit3 是第一个 0。x 1 0b1100024进位把低三位清成 0把 bit3 变成 1。这时候 x | (x 1) 0b10111 | 0b11000 0b1111131相当于是让 bit3 从 0 变成了 1低三位依然保持原来的 1。这个观察的威力在于它把“求一个函数值”变成“找二进制里的一个特征位置”。而反向构造就成了在目标 y 里找出刚才那个被改过的 0 位。2.3 立刻得到一个硬性结论偶数无解因为 f(x) 不管最低 0 位出现在哪里最低位 bit0 要么本来已经是 1要么由 0 变 1。所以 f(x) 永远是奇数。反过来如果 nums[i] 是偶数直接不可能有解答案就是 -1。这个结论看起来简单但代码里如果漏掉后面用 __builtin_ctz 很容易出错。想一下nums[i] 如果是偶数说明它的最低位是 0你拿它去套“连续尾 1”的公式会得到 r 0然后出现 1 (r - 1) 这种右移负数的未定义行为。所以偶数判断必须放在最前面。3. 反向构造的最小值证明为什么答案是 y 减掉 2^(r-1)3.1 用连续尾 1 的长度定位候选位置既然 y 必须是奇数我们只看奇数。设 r 是 y 从 bit0 开始第一个 0 的位置。因为 y 是奇数bit0 1所以至少 r 1从 bit0 到 bit(r - 1) 全是 1bit r 是 0。换句话说r 就是 y 二进制末尾连续 1 的个数。现在假设存在一个 x让 f(x) y。设 x 里被改的那个 0 位是 t。由于 t 是 x 的最低 0 位x 的 bit0 到 bit(t-1) 一定全是 1f(x) 后bit t 变成 1。因此 y 的 bit0 到 bit t 也全部是 1。如果 t 已经大于等于 r那么 y 的 bit r 会是 1但按定义 y 的 bit r 是 0矛盾。于是 t 的取值范围被死死限制在0 t r - 1这是一个关键收敛解的数量最多只有 r 个而不是无穷多个。例如 y 23二进制是 10111连续尾 1 长度 r 3那么 t 只能取 0、1、2。3.2 每个候选解长什么样对每一个合法的 t反向操作就是把 y 的 bit t 重新改回 0其它位保持不动。写成x_t y ^ (1 t)由于 y 在 bit t 处本来就是 1异或清零等价于减去 2^t。这些 x_t 全部合法吗验证一下x_t 的 bit0 到 bit(t-1) 仍然是 1bit t 是 0所以 x_t 的最低 0 位确实就是 t。对它执行 fbit t 变 1其余位不变恰好回到 y。拿 y 23 举例子三个候选分别是t 0x 22二进制 1011022 | 23 23t 1x 21二进制 1010121 | 22 23t 2x 19二进制 1001119 | 20 23三个都成立这时候问题就变成了选哪一个能让 x 最小。3.3 最小解的选择比较候选解的本质是在问把 y 的第几位清 0减掉的值最大因为 y 在 bit t 是 1所以x_t y - 2^t显然 t 越大减掉的 2^t 越大结果越小。因此最小解取 t r - 1也就是ans y - 2^(r - 1)把这个公式带回刚才的例子23 - 4 19确实是三个候选里的最小。再多试几个y 7二进制 111r 3ans 7 - 4 33 | 4 7y 13二进制 1101r 1ans 13 - 1 1212 | 13 13y 15二进制 1111r 4ans 15 - 8 77 | 8 15公式全部成立。3.4 这里最容易被绕晕的一点我踩过的坑是不要试图去找 y 的“最低 0 位”然后把它改成 1。我们是要在 y 的连续尾 1 里选一个位置改回 0不是改 y 的第一个 0。连续尾 1 长度 r 的求法有很多最方便的是借助 y 1因为 y 1 会把末尾的连续 1 全变成 0再把第一个 0 变成 1所以 y 1 的二进制末尾 0 个数恰好等于 r。例如 y 23y 1 24二进制 11000末尾 3 个 0r 3。在 C 里就是__builtin_ctz(y 1)在 Python 里用 lowbit 的位数。4. 三种实现与边界处理从暴力枚举到一行公式4.1 最直白的实现逐位找 r如果对内置函数不熟循环找 r 也完全够用vectorint constructArray(vectorint nums) { int n nums.size(); vectorint ans(n); for (int i 0; i n; i) { long long v nums[i]; if ((v 1LL) 0) { ans[i] -1; continue; } int r 0; while ((v r) 1LL) r; ans[i] (int)(v - (1LL (r - 1))); } return ans; }复杂度是 O(n * 31)对 LeetCode 的数据足够。用 long long 是为了防止移位越界和 INT_MAX 加 1 的问题。这里的 while 循环每轮最多跑 31 次因为 int 范围的正整数二进制位就这么多。4.2 用 __builtin_ctz 压缩到 O(n)vectorint constructArray(vectorint nums) { int n nums.size(); vectorint ans(n); for (int i 0; i n; i) { unsigned int v (unsigned int)nums[i]; if ((v 1u) 0) { ans[i] -1; continue; } int r __builtin_ctz(v 1u); ans[i] (int)(v - (1u (r - 1))); } return ans; }注意__builtin_ctz的参数是 unsigned int且参数为 0 时行为未定义。这里由于只处理奇数v 1 至少是 2不会为 0而转成 unsigned 之后INT_MAX 1 也定义良好。另一个容易错的地方是1 (r - 1)当 r - 1 达到 31 时int 的1 31是未定义行为所以要么用 unsigned要么直接用1LL ...。4.3 Python 版本甚至可以写成一行Python 没有直接的 ctz不过 lowbit 可以模拟(v 1) -(v 1)得到的是 v 1 的最低 1 位对应的值它的 2 的幂指数就是 r。而1 (r - 1)恰好等于 lowbit(v 1) 1。所以核心逻辑可以写成if v 1: ans[i] v - (((v 1) -(v 1)) 1) else: ans[i] -1验证 v 2324 -24 8右移一位得 423 - 4 19。验证 v 78 -8 8右移一位得 47 - 4 3。核心构造部分的代码就这一行。4.4 边界情况汇总输入情况处理方式原因nums[i] 为偶数答案 -1f(x) 一定是奇数nums[i] 0答案 -10 是偶数直接进入 -1 分支nums[i] 为奇数但很大比如 INT_MAX答案仍合法用 unsigned 或 long long 避免 1 溢出nums[i] 二进制全 1如 15公式照常工作连续尾 1 的范围就是整个二进制长度第一个 0 在更高位特别是最后一种情况比如 y 15二进制是 1111没有“中间”的 0 位但公式依然能算出 7。不要因为看到“找一个 0 位”就下意识认为全 1 的输入会出错。5. 把结论交给打表验证顺便聊聊这类题的迁移5.1 全量小数据暴力对照写公式最怕某个地方想当然所以我每次都会再补一段暴力验证。对 v 从 1 到 2000暴力枚举 x 从 0 到 v找最小的满足x | (x 1) v的数和公式结果比对。抽样结果v公式答案暴力最小 x结果100一致544一致733一致988一致1199一致131212一致1577一致171616一致231919一致如果你的代码跑完这一轮还能全过基本可以放心提交。注意暴力枚举里 x 0 也别忘了它和 x 1 这样的小值经常是答案。5.2 这套思路可以平移到哪些题位运算题里经常出现“某个操作只影响一个特征位”的形式比如x (x - 1)是去掉最低的 1x | (x 1)是填掉最低的 0x -x是提取最低的 1遇到这类操作第一步都是先明确它动了哪一位第二步反向构造就会简单很多。树状数组里的 lowbit、一些状态压缩题目里的末尾连续 1 统计本质上都在用同一个 ctz / trailing ones 概念。5.3 刷题时的个人习惯我现在的固定套路是拿到这种“构造最小 XX”的题先用小数据打表猜规律再回到二进制里验证最后才看题解。这道 3315 是我近期遇到的最典型一题题面短推导过程也不长但能把“枚举找答案”和“找规律直接算答案”两种思路对比得很清楚。如果你最近刷 BFS 刷得多偶尔换换位运算构造题反而会觉得思路清爽不少。不过这类题的共同原则是别急着套模板先把操作的本质写出来。最后再分享一个小技巧比赛里如果时间紧不必先写严格的数学证明。你可以先写暴力观察是不是只有 -1 和y - 2^(r - 1)两种输出确认之后再单独写一版 O(n) 的公式实现最后用暴力版本做差分对照。我提交前把 1 到 100000 的暴力结果和公式结果全部对了一遍确认没有边界漏网才敢上 O(n) 版本。这个流程虽然多写了十几行代码但能省下很多 Debug 时间。这就是我处理 3315 的全部经验希望对你有用。
