题目

给你一个长度为 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] 是一个质数。

解题思路

子定义：x + 1 会找到 x 二进制表示中最低位的 0，将其变为 1，并将该位右边的所有 1 变为 0（进位效应）。
OR 的作用：x | (x + 1) 会保留 x 原有的 1，同时把 x + 1 产生的进位后的那个高位 1 也补进来。
物理意义：x | (x + 1) 的结果，等价于把 x 二进制中最低位的那个 0 填补成 1。

推论：这意味着结果 nums[i] 的二进制形式，从最低位（LSB）开始，必须拥有一段连续的 1。

题目给定 nums[i] 是质数。

Case 1: 偶质数 2 (10₂)
- 二进制末尾是 0。
- 而算子 x | (x + 1) 必然导致最低位变为 1（因为 0 | 1 = 1，或者 1 | 0 = 1）。
- 结论：结果恒为奇数，不可能生成 2。直接返回 -1。
Case 2: 奇质数 (3, 5, 7, 11...)
- 所有奇数的二进制最低位（第0位）一定是 1。
- 这满足了“从最低位开始有一段连续的 1”这个必要条件（哪怕只有第0位这一个1）。
- 结论：所有奇质数都有解。

假设奇质数 nums[i] 的二进制末尾有 $k$ 个连续的 1。

即：$nums[i] = (\dots 0 \underbrace{11\dots1}_{k \text{个}}) _2$

我们要寻找一个 $x$，使得 $x$ 填补了最低位 $0$ 后变成 $nums[i]$。

这意味着 $x$ 和 $nums[i]$ 只有 1 个 bit 的区别，且这个 bit 必须位于那 $k$ 个连续的 1 之中。

构造候选集：我们可以把这 $k$ 个 1 中的任意一个变为 0，作为 $x$。这样 $x$ 的最低位 $0$ 就在那个位置，执行 x | (x+1) 就会把它填回 1，还原成 $nums[i]$。
最小化目标：$x = nums[i] - 2^p$ （其中 $p$ 是那 $k$ 个 1 所在的位移）。要使 $x$ 最小，必须让减去的 $2^p$ 最大。
策略：在末尾连续的 $k$ 个 1 中，选取最高位（Most Significant Bit within the run）对应的那个 1 将其翻转为 0。这个位的索引是 $k-1$（从0开始计数）。

具体代码

func minBitwiseArray(nums []int) []int {

    ans := make([]int, len(nums))
    for i, num := range nums {
        if num == 2 {
            ans[i] = -1
        } else {
            t := 0
            for num & 1 == 1 {
                t++
                num = num >> 1
            }
            ans[i] = nums[i] - (1 << (t - 1))
        }
    }
    return ans
}

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

beautifulremi

题目

解题思路

具体代码