这是 LeetCode 3806 Maximum Bitwise AND After Increment Operations 的 Python 实现。

解题思路

贪心逐位构造：从高到低枚举每一位，尝试将当前位加入答案。

对于候选值 `target`，需要判断是否存在大小为 `m` 的子集，使得总操作次数不超过 `k`。关键是计算每个 `nums[i]` 提升到包含 `target` 所有 1 位的最小代价：

- `diff = target & ~nums[i]`：`target` 为 1 但 `nums[i]` 为 0 的位
- 若 `diff == 0`，代价为 `0`（已满足）
- 否则设 `j` 为 `diff` 的最高位，只需补齐低 `j+1` 位：
  - `mask = (1 << (j+1)) - 1`
  - `y = (nums[i] & ~mask) | (target & mask)`
  - `cost = y - nums[i]`

取最小的 `m` 个代价之和，若不超过 `k` 则该位可行。

```python
from typing import List

class Solution:
    def maximumAND(self, nums: List[int], k: int, m: int) -> int:
        max_val = max(nums) + k
        mx = max_val.bit_length()   # 需要检查的最高位数
        n = len(nums)
        ans = 0
        
        for bit in range(mx - 1, -1, -1):
            target = ans | (1 << bit)
            cost = []
            zero_cnt = 0
            
            for x in nums:
                diff = target & ~x
                if diff == 0:
                    zero_cnt += 1      # 已包含 target 的所有 1 位
                else:
                    j = diff.bit_length() - 1   # diff 最高位索引
                    mask = (1 << (j + 1)) - 1
                    y = (x & ~mask) | (target & mask)
                    cost.append(y - x)
            
            # 已有 m 个数无需操作即可满足
            if zero_cnt >= m:
                ans = target
                continue
            
            cost.sort()
            # 从需要操作的数中选 (m - zero_cnt) 个最小的
            if sum(cost[:m - zero_cnt]) <= k:
                ans = target
        
        return ans
```

复杂度

- 时间：O(\log(\max) \cdot n \log n)，其中 \max = \max(nums) + k
- 空间：O(n)