E3314.构造最小位运算数组 I

https://leetcode.cn/problems/construct-the-minimum-bitwise-array-i/

给你一个长度为 n 的质数数组 nums 。你的任务是返回一个长度为 n 的数组 ans ，对于每个下标 i ，以下 条件 均成立：

• ans[i] OR (ans[i] + 1) == nums[i]

除此以外，你需要 最小化 结果数组里每一个 ans[i] 。

如果没法找到符合 条件 的 ans[i] ，那么 ans[i] = -1 。

质数 指的是一个大于 1 的自然数，且它只有 1 和自己两个因数。

示例 1：

输入：nums = [2,3,5,7]

输出：[-1,1,4,3]

解释：

• 对于 i = 0 ，不存在 ans[0] 满足 ans[0] OR (ans[0] + 1) = 2 ，所以 ans[0] = -1 。
• 对于 i = 1 ，满足 ans[1] OR (ans[1] + 1) = 3 的最小 ans[1] 为 1 ，因为 1 OR (1 + 1) = 3 。
• 对于 i = 2 ，满足 ans[2] OR (ans[2] + 1) = 5 的最小 ans[2] 为 4 ，因为 4 OR (4 + 1) = 5 。
• 对于 i = 3 ，满足 ans[3] OR (ans[3] + 1) = 7 的最小 ans[3] 为 3 ，因为 3 OR (3 + 1) = 7 。

示例 2：

输入：nums = [11,13,31]

输出：[9,12,15]

解释：

• 对于 i = 0 ，满足 ans[0] OR (ans[0] + 1) = 11 的最小 ans[0] 为 9 ，因为 9 OR (9 + 1) = 11 。
• 对于 i = 1 ，满足 ans[1] OR (ans[1] + 1) = 13 的最小 ans[1] 为 12 ，因为 12 OR (12 + 1) = 13 。
• 对于 i = 2 ，满足 ans[2] OR (ans[2] + 1) = 31 的最小 ans[2] 为 15 ，因为 15 OR (15 + 1) = 31 。

提示：

• 1 <= nums.length <= 100
• 2 <= nums[i] <= 1000
• nums[i] 是一个质数。

这个问题要求我们找到最小的整数 $ans[i]$，使得 $ans[i]\vee (ans[i]+1)=nums[i]$。

算法分析

1. 位运算性质： 考察表达式 $x\vee (x+1)$：

   • 如果 $x$ 的二进制表示以 $k$ 个连续的 $1$ 结尾（即 $x=\dots 0\underset{k}{\underbrace{11\dots 1}}$），那么 $x+1$ 的二进制表示将会是 $\dots 1\underset{k}{\underbrace{00\dots 0}}$。
   • 此时 $x\vee (x+1)=(\dots 011\dots 1)\vee (\dots 100\dots 0)=\dots 111\dots 1$。
   • 结果是将 $x$ 从右往左数第一个 $0$ 变成 $1$。

2. 推导规律： 已知 $nums[i]$ 是质数。

   • 如果 $nums[i]=2$（二进制 10）：它是唯一的偶质数。因为 $x\vee (x+1)$ 的结果必然是奇数（末位一定是 $1$），所以 $2$ 无法由该表达式得出，返回 $-1$。
   • 如果 $nums[i]$ 是奇数：它的二进制表示一定以 $1$ 结尾。为了让 $ans[i]$ 最小，我们需要找到 $nums[i]$ 末尾连续的 $1$。
     • 假设 $nums[i]$ 末尾有 $k$ 个连续的 $1$。
     • 根据上面的性质，如果我们把这 $k$ 个 $1$ 中最高位的那个 $1$ 变成 $0$，得到的数就是满足条件的最小 $ans[i]$。
     • 例如：$nums[i]=7$ (二进制 111)，末尾有 $3$ 个 $1$。将从右数第 $3$ 位（权值为 $2^{3-1}=4$）的 $1$ 变 $0$，得到 $7-4=3$ (二进制 011)。
     • 验证：$3\vee (3+1)=3\vee 4=7$。

3. 具体步骤：

   • 遍历 nums 中的每个数 $n$。
   • 若 $n=2$，结果为 $-1$。
   • 否则，从低位向高位查找 $n$ 的二进制中末尾连续 $1$ 的个数 $k$。
   • 计算 $ans=n-2^{k-1}$ 或 $ans=n\oplus (1\ll (k-1))$。

代码实现

class Solution:
    def minBitwiseArray(self, nums: List[int]) -> List[int]:
        ans = []
        for n in nums:
            if n == 2:
                ans.append(-1)
            else:
                # 寻找末尾连续 1 的个数
                k = 0
                temp = n
                while temp & 1:
                    k += 1
                    temp >>= 1
                
                # 将第 k-1 位（从0开始）的 1 变为 0
                # 例如 n=7 (111), k=3, 结果应为 7 - 2^(3-1) = 3 (011)
                ans.append(n - (1 << (k - 1)))
        return ans

复杂度分析

• 时间复杂度：$O(N\times \log (max(nums)))$，其中 $N$ 是数组长度。由于 $nums[i]\le 1000$，$\log (nums[i])$ 最大约为 $10$，因此计算非常快。
• 空间复杂度：$O(1)$，除了存储结果所需的数组外，仅使用了常数空间。

class Solution:
    def minBitwiseArray(self, nums: List[int]) -> List[int]:
        ans = []
        for n in nums:
            if n == 2:
                ans.append(-1)
            else:
                # n is odd prime >= 3
                low = (n + 1) & -(n + 1)  # lowest set bit of (n+1)
                x = n - low // 2
                ans.append(x)
        return ans

这份代码本质上是利用位运算技巧更高效地寻找末尾连续的 1。

它的核心逻辑和我之前提供的“寻找 $k$ 个连续的 1”是完全一致的，只不过它避开了 while 循环，直接通过位运算公式一步到位。

我们可以通过一个具体的例子来拆解这段代码的逻辑。

核心位运算技巧：x & -x

在位运算中，x & -x 是一个经典的技巧，它能提取出整数 x 二进制表示中最低位的 1（Lowest Set Bit）及其后面的 0。

例如：

• 若 $x=12$（二进制 1100），则 12 & -12 = 4（二进制 0100）。
• 若 $x=8$（二进制 1000），则 8 & -8 = 8（二进制 1000）。

代码逻辑推导

假设 $nums[i]=11$，其二进制为 1011。

1. 第一步：n + 1

   • $11+1=12$。
   • 二进制变化：1011 $\to$ 1100。
   • 关键点：当一个末尾全是 $1$ 的数加 $1$ 时，这些 $1$ 会全部进位变成 $0$，而紧邻它们左边的那个 $0$ 会变成 $1$。

2. 第二步：low = (n + 1) & -(n + 1)

   • 计算 $12$ 的最低位 $1$。
   • $12$ (1100) 的最低位 $1$ 是从右数第三位，权值为 $4$。
   • 这个 low (即 $4$) 对应的位置，正好是 n (即 $11$) 从右往左数第一个 0 的位置。

3. 第三步：low // 2

   • low // 2 = 4 // 2 = 2。
   • 在二进制中，low // 2 就是把那个 $1$ 向右移动一位。
   • 这个位置对应的正好是 n (即 $11$) 末尾那串连续 $1$ 中的最高位。

4. 第四步：x = n - low // 2

   • $11-2=9$。
   • 二进制：1011 - 0010 = 1001。
   • 这步操作成功地把 n 末尾连续 $1$ 中的最高位从 $1$ 变成了 $0$。

总结对照

概念	你的代码写法	我的代码写法
末尾 1 的个数	无需计算具体个数 $k$	循环得到 $k$
末尾 1 中最高位的权值	low // 2	1 << (k - 1)
操作目标	将该位的 1 变 0	将该位的 1 变 0

示例走读：n = 7 (二进制 111)

1. n + 1 = 8 (二进制 1000)
2. low = 8 & -8 = 8 (最低位的 1 是 8)
3. low // 2 = 4 (对应 7 的二进制 111 中左起第一个 1)
4. ans = 7 - 4 = 3 (二进制 011)
5. 验证：$3\vee (3+1)=3\vee 4=7$。正确。

结论：这份代码使用了 (n+1) & -(n+1) 巧妙地定位了需要修改的那一位，避免了循环，在性能上更优（虽然在 LeetCode 这道题的量级下差别不大），是一种更“硬核”的写法。