2026-05-19：增加操作后最大按位与的结果。用go语言，已知一个整数数组 nums，以及两个整数 k 和 m。你可以进行至多 k 次操作：每次操作

2026-05-19：增加操作后最大按位与的结果。用go语言，已知一个整数数组 nums，以及两个整数 k 和 m。你可以进行至多 k 次操作：每次操作你可以选定数组中的某个位置 i，把 nums[i] 的值增加 1。

在最多做完这 k 次操作之后，从数组里任意挑选出 m 个元素组成一个子集（子集大小固定为 m），对这 m 个元素做按位与运算。你的目标是：让这个按位与的结果尽可能大。问最大的可能值是多少。

1 <= n == nums.length <= 50000。

1 <= nums[i] <= 1000000000。

1 <= k <= 1000000000。

1 <= m <= n。

输入： nums = [3,1,2], k = 8, m = 2。

输出： 6。

解释：

我们需要一个大小为 m = 2 的子集。选择下标 [0, 2]。

使用 3 次操作将 nums[0] = 3 增加到 6，并使用 4 次操作将 nums[2] = 2 增加到 6。

总共使用的操作次数为 7，不大于 k = 8。

这两个选定的值变为 [6, 6]，它们的按位与结果是 6，这是可能的最大值。

题目来自力扣3806。

算法执行详细步骤 一、问题核心理解

1. 操作规则：最多把数组中元素总共加 k 次 1（可以给任意元素加）

2. 目标：操作完成后，选 m 个元素，让它们的按位与结果最大

3. 按位与特性：二进制位上所有数该位都是 1，结果该位才是 1；只要有一个是 0，结果就是 0。因此我们要从高位到低位，贪心尝试把每一位变成 1。

二、第一步：预处理与边界判断

1.排序数组：把 nums 从小到大排序，得到[1,2,3]

2.计算理论最大可能值：最大的数 + k/m（平均分配操作次数），这里 3+8/2=7，最终答案一定不超过 7

3.特殊情况判断：检查最大的 m 个数是否全部相等

• 本例最大 2 个数是 2、3，不相等，跳过特殊逻辑

三、核心算法：高位优先贪心构造答案（按二进制位从高到低尝试）

二进制位数：理论最大值 7 是 3 位二进制（111），我们从**最高位（第2位）→ 最低位（第0位）**依次尝试：
初始答案ans = 0（二进制 000），目标是尽可能把每一位变成 1。

第1轮：尝试设置 最高位（第2位，值=4，二进制 100）

1. 构造目标值：当前答案 | 4 →0 | 4 = 4（二进制 100）

2. 计算把每个数变成至少满足目标值需要的操作次数

• 规则：只需要保证数的二进制高位和目标一致，计算最小加1次数

• 1 → 满足 4 需要加 3 次

• 2 → 满足 4 需要加 2 次

• 3 → 满足 4 需要加 1 次

3. 排序操作次数：[1,2,3]

4. 选最小的 m=2 个次数求和：1+2=3

5. 验证：3 ≤ 8（总操作数k）→该位可以设为1

6. 更新答案：ans = 4（二进制 100）

第2轮：尝试设置 次高位（第1位，值=2，二进制 010）

1. 构造目标值：当前答案(4) | 2 →6（二进制 110）

2. 计算把每个数变成至少满足 6 需要的操作次数

• 1 → 变成6需要加5次

• 2 → 变成6需要加4次

• 3 → 变成6需要加3次

3. 排序操作次数：[3,4,5]

4. 选最小的 m=2 个次数求和：3+4=7

5. 验证：7 ≤ 8 →该位可以设为1

6. 更新答案：ans = 6（二进制 110）

第3轮：尝试设置 最低位（第0位，值=1，二进制 001）

1. 构造目标值：当前答案(6) | 1 →7（二进制 111）

2. 计算把每个数变成至少满足7需要的操作次数

• 1 → 变成7需要加6次

• 2 → 变成7需要加5次

• 3 → 变成7需要加4次

3. 排序操作次数：[4,5,6]

4. 选最小的 m=2 个次数求和：4+5=9

5. 验证：9 > 8（超过总操作数）→该位不能设为1

6. 答案保持不变：ans 仍为 6

四、最终结果

所有位尝试完毕，最终最大按位与结果为6，和题目示例完全一致。
（操作方案：把3→6（3次）、2→6（4次），总7次≤8，两个数按位与=6）

时间复杂度 & 额外空间复杂度 1. 总时间复杂度

O(W × n log n)

• W：二进制最大位数（固定值，约30~32位，因为数值上限1e9）

• n：数组长度

• 核心耗时：每一轮都要对长度为n的操作次数数组排序（O(n log n)），共执行W轮

• 整体复杂度：线性对数级，完全适配题目 n≤5e4 的限制

2. 总额外空间复杂度

O(n)

• 仅开辟了一个长度为n的数组ops，用于存储每个数的操作次数

• 其余变量都是常数级空间，不随输入规模变化

• 空间复杂度：线性级

总结

1. 核心思路：高位贪心，从最高位到最低位依次尝试能否将该位设为1，能则保留，不能则跳过

2. 关键判断：计算让 m 个数满足目标值的最小操作次数总和，不超过k则该位有效

3. 时间复杂度：O(32 × n log n)，高效处理大数据量

4. 空间复杂度：O(n)，仅使用一个辅助数组存储操作次数

Go完整代码如下：

package main

 import (
    "fmt"
    "math/bits"
    "slices"
)

 func maximumAND(nums []int, k, m int) (ans int) {
    slices.Sort(nums)
    n := len(nums)
    maxAns := nums[n-1] + k/m
    if nums[n-m] == nums[n-1] { // 最大的 m 个数都相等
        return maxAns
    }

     ops := make([]int, n) // 每个数的操作次数
    maxWidth := bits.Len(uint(maxAns))
    for bit := maxWidth - 1; bit >= 0; bit-- {
        target := ans | 1< 
 
 // 注意 target 要带着 ans 已经填好的 1 
 
 
          
 for 
  i, x :=  
 range 
  nums { 
 
 
             j := bits.Len( 
 uint 
 (target &^ x)) 
 
 
              
 // j-1 是从高到低第一个 target 是 1 且 x 是 0 的比特位 
 
 
              
 // target = 10110 
 
 
              
 //      x = 11010 
 
 
              
 //            ^ 
 
 
              
 //           j-1 
 
 
              
 // x 二进制中的高于 j-1 的位不变，其余位增大到和 target 一样 
 
 
              
 // 上面的例子要把 010 变成 110 
 
 
             mask :=  
 1 
 < 
 
 1 
 
 
             ops[i] = target&mask - x&mask 
 
 
         } 
 
 
 
 
          
 // 贪心，取前 m 小的操作次数 
 
 
         slices.Sort(ops) 
 
 
         sum :=  
 0 
 
 
          
 for 
  _, x :=  
 range 
  ops[:m] { 
 
 
             sum += x 
 
 
         } 
 
 
          
 if 
  sum <= k { 
 
 
             ans = target  
 // 答案的 bit 位可以填 1 
 
 
         } 
 
 
     } 
 
 
      
 return 
 
 
 } 
 
 
 
 
 func main() 
  { 
 
 
     nums := [] 
 int 
 { 
 3 
 ,  
 1 
 ,  
 2 
 } 
 
 
     k :=  
 8 
 
 
     m :=  
 2 
 
 
     result := maximumAND(nums, k, m) 
 
 
     fmt.Println(result) 
 
 
 } 
 
 
 
 

Python完整代码如下：

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

 def maximumAND(nums, k, m):
    nums.sort()
    n = len(nums)
    maxAns = nums[n-1] + k // m
    # 最大的 m 个数都相等
    if nums[n-m] == nums[n-1]:
        return maxAns
    ans = 0
    ops = [0] * n  # 每个数的操作次数
    maxWidth = maxAns.bit_length()
    for bit in range(maxWidth - 1, -1, -1):
        target = ans | (1 << bit)  # 注意 target 要带着 ans 已经填好的 1
        for i, x in enumerate(nums):
            # j 是从高到低第一个 target 是 1 且 x 是 0 的比特位
            # 计算 target &^ x 的最高位位置
            diff = target & ~x
            if diff == 0:
                j = 0
            else:
                j = diff.bit_length()
            # x 二进制中的高于 j-1 的位不变，其余位增大到和 target 一样
            mask = (1 << j) - 1
            ops[i] = (target & mask) - (x & mask)
        # 贪心，取前 m 小的操作次数
        ops.sort()
        total_sum = sum(ops[:m])
        if total_sum <= k:
            ans = target  # 答案的 bit 位可以填 1
    return ans

 if __name__ == "__main__":
    nums = [3, 1, 2]
    k = 8
    m = 2
    result = maximumAND(nums, k, m)
    print(result)

C++完整代码如下：

  

  

   

  


 using namespace std;

 int maximumAND(vector& nums, int k, int m) {
    sort(nums.begin(), nums.end());
    int n = nums.size();
    int maxAns = nums[n - 1] + k / m;

     // 最大的 m 个数都相等
    if (nums[n - m] == nums[n - 1]) {
        return maxAns;
    }

     int ans = 0;
    vector ops(n, 0);  // 每个数的操作次数
    int maxWidth = 32 - __builtin_clz(maxAns);  // 计算二进制位数

     for (int bit = maxWidth - 1; bit >= 0; bit--) {
        int target = ans | (1 << bit);  // 注意 target 要带着 ans 已经填好的 1

         for (int i = 0; i < n; i++) {
            int x = nums[i];
            // 计算 target & ^x 的最高位位置
            int diff = target & ~x;
            int j = 0;
            if (diff != 0) {
                j = 32 - __builtin_clz(diff);  // 计算 diff 的二进制位数
            }
            // j-1 是从高到低第一个 target 是 1 且 x 是 0 的比特位
            // target = 10110
            //      x = 11010
            //            ^
            //           j-1
            // x 二进制中的高于 j-1 的位不变，其余位增大到和 target 一样
            // 上面的例子要把 010 变成 110
            int mask = (1 << j) - 1;
            ops[i] = (target & mask) - (x & mask);
        }

         // 贪心，取前 m 小的操作次数
        sort(ops.begin(), ops.end());
        int sum = 0;
        for (int i = 0; i < m; i++) {
            sum += ops[i];
        }

         if (sum <= k) {
            ans = target;  // 答案的 bit 位可以填 1
        }
    }

     return ans;
}

 int main() {
    vector nums = {3, 1, 2};
    int k = 8;
    int m = 2;
    int result = maximumAND(nums, k, m);
    cout << result << endl;
    return0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。