2025-05-09：构造最小位运算数组Ⅰ。用go语言，给定一个长度为 n 的质数数组 nums，要求构造一个同样长度为 n 的数组 ans，使得对于每个索引 i，满足以下条件：

• ans[i] 与 ans[i] + 1 进行按位或操作后的结果等于 nums[i]，即 ans[i] OR (ans[i] + 1) == nums[i]。

• 在满足上述条件的 ans[i] 中，选择最小的那个值。

如果不存在符合条件的 ans[i]，则将 ans[i] 设为 -1。

这里的质数指的是大于1且仅有两个正因数的自然数。

1 <= nums.length <= 100。

2 <= nums[i] <= 1000。

nums[i] 是一个质数。

输入：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 。

题目来自leetcode3314。

分步过程描述：

1. 分析条件：对于每个数nums[i]，寻找最小的ans[i]使得ans[i] OR (ans[i] + 1) = nums[i]。需要理解按位或操作的性质，特别是当两个连续的数进行或运算时，结果的特点。

2. 全1情况判断：如果nums[i] + 1是2的幂次方，则说明nums[i]的二进制形式全为1。此时，最小ans[i]为(nums[i] - 1) / 2。例如，nums[i] = 3对应二进制11，此时ans[i] = 1。

3. 非全1情况处理：当nums[i]的二进制不全为1时，遍历可能的x值（从0到nums[i] - 1），找到满足x OR (x + 1) = nums[i]的最小x。例如，nums[i] = 5时，遍历到x = 4满足条件。

4. 不存在解的情况：如果遍历所有可能的x后仍未找到符合条件的值，则将ans[i]设为-1。例如，nums[i] = 2时，没有解。

5. 示例验证：按照上述步骤处理输入示例[2, 3, 5, 7]：

   • 对于2，无解，返回-1。
   • 对于3，满足全1条件，返回1。
   • 对于5，遍历找到x=4满足条件。
   • 对于7，满足全1条件，返回3。

时间复杂度：假设数组长度为n，每个元素最大值为k，则总时间复杂度为O(nk)，即O(1001000)=1e5，属于线性复杂度，效率较高。

额外空间复杂度：除输入和输出数组外，仅使用常数空间，因此为O(1)。

Go完整代码如下：

package main

import (
	"fmt"
)

func minBitwiseArray(nums []int) []int {
	for i, x := range nums {
		if x == 2 {
			nums[i] = -1
		} else {
			nums[i] ^= (x + 1) &^ x >> 1
		}
	}
	return nums
}

func main() {
	nums := []int{2, 3, 5, 7}
	result := minBitwiseArray(nums)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

from typing import List

def min_bitwise_array(nums: List[int]) -> List[int]:
    for i, x in enumerate(nums):
        if x == 2:
            nums[i] = -1
        else:
            nums[i] = x ^ (((x + 1) & (~x)) >> 1)
    return nums

if __name__ == "__main__":
    nums = [2, 3, 5, 7]
    result = min_bitwise_array(nums)
    print(result)