一开始以为是贪心，但是贪不了。

题面

给你一个长度为 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 $\le$ nums.length $\le$ 100
• 2 $\le$ nums[i] $\le$ $10^9$
• nums[i] 是一个质数。

思路

那么一开始的思路是什么？贪心硬算。然后被后面No.600多的超大测试点吓懵了

后面发现这边要利用二进制位运算的一些特性。

此处参考了 @灵茶山艾府 的讲解视频，下面也有引用。

$x ∣ (x+1)$的最终目的是把最终二进制数末的 0 全都变成 1 。既然已经变成了1，则nums[i]里能匹配到的数就一定是奇数，所以排除 i%2==0 的情况。

题面里又要求最小化 ans[i]，这里利用取反右移，忽略前面的0，将原数与其做异或计算，即可得到答案要求的数。

代码

class Solution {
public:
    vector<int> minBitwiseArray(vector<int>& nums) {
        vector<int> ans;
        for(int i:nums){
            if(i % 2 == 0){
                ans.push_back(-1);
                continue;
            }
            int tmp = ~i;
            int tmp_a = i;
            tmp_a ^= (tmp & -tmp) >> 1;
            ans.push_back(tmp_a);
        }
        return ans;
    }
};

后记

位运算好啊，位运算要做啊。

差点就拿贪心暴力做了。

但是冒出来个这么长的，很明显没法暴

[708152587,378138253,696612107,843995171,377416939,511045259,683858689,337171363,220344211,144177239,486997853,290548319]

附一段之前暴力时候的错误代码。

class Solution {
public:
    vector<int> minBitwiseArray(vector<int>& nums) {
        vector<int> ans;
        for(int i:nums){
            for(int p=1;;p++){
                int tmp = p | (p+1);
                // printf("%d | %d = %d, i:%d\n",p,p+1,tmp,i);
                if(p>i){
                    ans.push_back(-1);
                    break;
                }else if(tmp==i){
                    ans.push_back(p);
                    break;
                }
            }
        }
        return ans;
    }
};

不要学我。