发表于 2026.02.06

• 位运算的题目，数组nums的元素为质数并没有太多特殊的含义，只是告诉你除了2之外，其他必然为奇数（也就是二进制表示法中，必定以1比特位结尾）。对于给出的条件ans[i] OR (ans[i] + 1)，不难想到对于任意整数x，x OR (x + 1)的效果是将x从右往左数遇到的第一个二进制0变为1（比如，对于a = 111000011，那么a + 1 = 111000100，a OR a + 1即111000111，就是将最低位0反转成1）。因此，要让等式成立，意味nums[i]必然是将某个数的最低位0变1得到的，而这个数的最低位左侧的比特位和nums[i]是一致的。

  根据上述规律，nums[i]的二进制形式一定是...011...1（最后以连续的1结尾）。要构造最小的ans[i]，最优做法是找到 nums[i] 末尾这一串连续1中最高位置的那个1，并将其变为0。例如，如果nums[i]的二进制末尾是...0111，那么对应的最小ans[i]就是...0011。在代码实现上，可以通过位移操作定位到从右往左第一个0的位置，然后将该位右侧的1抹除即可。

  比如，对于11100001111，那么其最优解是11100000111，其加1会变成11100001000（不断进位，直至遇到0），两者OR操作后会变成11100001111。还能有更小的解吗？没有了，毕竟前面的0不能改成1（比如11010001111）（OR的特点，有1的位，必然结果都会有1，必然凑不成原来的数字）；将更前面的1改成0（比如11000001111），其加1后，也不能将前面改成的0翻转回去1，所以也凑不成原来的数字。

  class Solution {
  public:
      vector<int> minBitwiseArray(vector<int>& nums) {
          vector<int> ans(nums.size(), -1);
          for (int i = 0; i < nums.size(); ++i) {
              if (nums[i] == 2) continue;
              int mask = 1;
              // 从右到左寻找尾部连续1的最左位 -> 寻找第一个0bit
              while (mask & nums[i]) {
                  mask <<= 1;
              }
              mask >>= 1;
              ans[i] = nums[i] - mask;  // 将这个1抹为0即为解
          }
          return ans;
      }
  };

• LC 题目链接