LeetCode 3315. 构造最小位运算数组 II 位运算解法

1. 整体思路与数学推导

核心问题

对于输入的每个数字 x，我们需要找到一个数 ans[i]，满足特定的位运算性质。通过逆向工程代码逻辑： ans[i] = x - (lowbit(~x) >> 1) 这意味着我们正在寻找 x 的二进制表示中，最低位的连续 1 序列，并将该序列中最高位的那个 1 变成 0。

逻辑推导

1. 观察 y | (y + 1) 的性质：
   • 设 y 的二进制表示为 ...011...1（最低位有 k 个连续的 1，前面是 0）。
   • 那么 y + 1 会变成 ...100...0（进位，最低位 k 个 1 变 0，前面的 0 变 1）。
   • 做按位或运算 y | (y + 1)，结果最低的 k + 1 位都会变成 1。
   • 结论：y | (y + 1) 的结果 x 一定是形如 ...111...1 的，即它必须以连续的 1 结尾，且至少有一个 0 在这个序列之前（或者是全 1）。
   • 更准确地说，y | (y + 1) 的操作是将 y 二进制中最低位的那个 0 变成了 1。
2. 逆向求解 y (即代码中的 ans)：
   • 如果 x 是由某个 y 转换而来的，那么 x 必然是由 y 把最低位的 0 变成 1 得到的。
   • 要还原最小的 y，我们只需要把 x 中最低位的连续 1 序列中的最高位那个 1 还原回 0 即可。
   • 例如：x = 10111_2 (23)。
     • 最低位连续的 1 是最后的 111。
     • 我们要找的 y 应该是 10011。因为 10011 | 10100 = 10111。
     • 变换方法：找到 x 中第一个 0 的位置（从低位起），它的右边一位就是我们要变成 0 的那个 1。
3. 位运算技巧：
   • ~x：取反。x 中最低的连续 1 变成连续 0，紧接着的那个 0 变成 1。
   • t = ~x，lowbit = t & -t：提取出 t 中最低位的 1。这个 1 的位置对应 x 中最低位连续 1 序列左边紧邻的那个 0 的位置。
   • lowbit >> 1：右移一位。这正好对应 x 中最低位连续 1 序列中最高位的那个 1 的权重。
   • x - (lowbit >> 1)：从 x 中减去这个权重，即将那个 1 变成 0。
4. 特殊情况 x = 2：
   • 如果 x = 2 (10_2)，它是偶数。
   • 根据 y | (y + 1) 的性质，结果一定包含最低位的 1（因为 y 或 y + 1 必有一个是奇数，导致最低位为 1）。

2. 完整代码

import java.util.List;

class Solution {
    public int[] minBitwiseArray(List<Integer> nums) {
        int n = nums.size();
        [] ans =  [n];
        
         (   ; i < n; i++) {
               nums.get(i);
            
            
            
             (x == ) {
                ans[i] = -;
            }  {
                
                
                
                
                   ~x;
                
                
                
                   t & -t;
                
                
                
                
                
                
                
                ans[i] = x - (lowbit >> );
            }
        }
         ans;
    }
}