2026-02-02：没有公共位的整数最大乘积。用go语言，给定一个整数数组 nums，选出两个不同位置的元素（下标不同），要求这两个数在二进制表示上没有共同为1的位（即它们按位与为0）。在所有满足该条件的数对中，求其乘积的最大值；如果没有任何符合条件的数对，则返回 0。

2 <= nums.length <= 100000。

1 <= nums[i] <= 1000000。

输入：nums = [64,8,32]。

输出：2048。

解释：

没有任意一对数字共享公共置位，因此答案是两个最大元素的乘积：64 和 32 (64 * 32 = 2048)。

题目来自力扣3670。

🧠 算法分步解析

步骤1：计算二进制位宽并确定阈值

• 首先，代码使用 bits.Len 和 slices.Max 找出数组中最大数字的二进制位宽（记为 w），即表示这些数字所需的最大比特数。例如，最大数为64（二进制1000000）时，w = 7。
• 计算 u = 1 << w，这定义了基于位宽的数值范围上界（u 是大于等于最大数的最小2的幂次）。例如，w=7 时 u=128。
• 设定一个阈值条件：如果 n*n <= u*w（即数组长度的平方小于等于范围上界与位宽的乘积），则采用暴力枚举法；否则采用更高效的**动态规划预处理（SOS DP）**方法。这是为了在数据规模较小时避免复杂预处理的开销。

步骤2：小规模情况——暴力枚举

• 当满足阈值条件时，算法使用双重循环检查所有不同的数对 (x, y)。
• 对于每一对数，检查它们按位与的结果是否为0（x & y == 0）。这个条件确保两个数的二进制表示没有任何一个比特位同时为1，即没有公共置位。
• 在所有满足条件的数对中，记录最大的乘积 x * y。
• 暴力枚举的时间复杂度为 O(n²)，但仅在 n 相对较小时使用。

步骤3：大规模情况——SOS DP预处理

如果数据规模较大，算法分三步利用位运算特性进行优化：

1. 初始化频率数组：

   • 创建一个长度为 u 的数组 f，初始时 f[x] = x。这个数组用于记录每个数值（作为比特掩码）对应的最大原始数（如果该数存在于 nums 中）。

2. SOS DP状态更新：

   • 使用Sum Over Subsets (SOS)动态规划技术，对每个比特掩码 s，计算其所有子集中在 nums 中出现过的最大数值。
   • 通过遍历每个比特掩码 s 及其子集来实现：对于每个 s，通过不断清除最低位的1（lb = t & -t 获取最低位的1，然后 t ^= lb 清除该位）来枚举其所有子集。更新 f[s] = max(f[s], f[s^lb])，确保 f[s] 存储了子集 s 所有子集中的最大值。

3. 查询最大乘积：

   • 对于数组中的每个数 x，计算其按位补码（相对于全u位）对应的掩码 mask = u-1 ^ x。这个掩码代表了所有不与 x 的置位冲突的比特位组合。
   • 查询 f[mask]，它给出了与 x 没有公共置位的最大数字（可能为0，表示不存在这样的数）。
   • 计算 x * f[mask] 并更新全局最大乘积 ans。

步骤4：返回结果

• 将计算得到的最大乘积 ans 转换为 int64 类型后返回。如果没有找到满足条件的数对，ans 将保持初始值0。

⏱️ 复杂度分析

时间复杂度

• 最坏情况（SOS DP）：SOS DP预处理的时间复杂度为 O(u * 2^w)，其中 u 是数值范围，w 是位宽。由于 u 和 w 由数组中的最大值决定（u 是大于最大值的2的幂，w 是其位宽），且最大值不超过1000000，因此 w 最大约为20，u 最大为2^20≈1e6。但实际中 w 通常较小，SOS DP步骤是主要开销。查询阶段为 O(n)。
• 最好情况（暴力枚举）：当 n 较小时，直接使用暴力枚举，时间复杂度为 O(n²)。
• 整体：算法通过阈值自适应选择策略，在数据规模不同时平衡预处理和查询开销。最坏情况由SOS DP主导。

空间复杂度

• 主要额外空间是SOS DP数组 f，其大小为 u。因此，额外空间复杂度为 O(u)，即数值范围的上界。

💎 核心思路总结

该算法的核心在于利用位掩码和SOS DP技术，将“寻找无公共置位的数对”转化为对子集极值的快速查询。通过自适应阈值选择暴力枚举或SOS DP，兼顾了不同数据规模下的效率。

Go完整代码如下：

package main

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

// 基于方法一
func maxProduct(nums []int) int64 {
	w := bits.Len(uint(slices.Max(nums)))
	u := 1 << w

	n := len(nums)
	if n*n <= u*w {
		// 暴力
		ans := 0
		for i, x := range nums {
			for _, y := range nums[:i] {
				if x&y == 0 {
					ans = max(ans, x*y)
				}
			}
		}
		return int64(ans)
	}

	f := make([]int, u)
	for _, x := range nums {
		f[x] = x
	}

	for s := range f {
		for t, lb := s, 0; t > 0; t ^= lb {
			lb = t & -t
			f[s] = max(f[s], f[s^lb])
		}
	}

	ans := 0
	for _, x := range nums {
		ans = max(ans, x*f[u-1^x])
	}
	return int64(ans)
}

func main() {
	nums := []int{64, 8, 32}
	result := maxProduct(nums)
	fmt.Println(result)
}

Python完整代码如下：

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

from typing import List
import math

def maxProduct(nums: List[int]) -> int:
    # 找到最大值并计算其二进制位数
    max_num = max(nums)
    w = max_num.bit_length()  # 相当于 Go 中的 bits.Len
    u = 1 << w  # 2^w
    
    n = len(nums)
    
    # 根据 n 的大小选择不同策略
    if n * n <= u * w:
        # 暴力枚举所有数对
        ans = 0
        for i, x in enumerate(nums):
            for y in nums[:i]:
                if x & y == 0:
                    ans = max(ans, x * y)
        return ans
    
    # 初始化数组 f，大小为 u
    f = [0] * u
    
    # 对于每个数字 x，f[x] 至少是 x
    for x in nums:
        f[x] = x
    
    # 动态规划：计算每个状态的最大值
    for s in range(u):
        t = s
        while t > 0:
            # 获取最低位的 1
            lb = t & -t
            # 更新 f[s] 为 f[s^lb] 和当前值的较大值
            f[s] = max(f[s], f[s ^ lb])
            # 移除最低位的 1
            t ^= lb
    
    # 计算结果
    ans = 0
    for x in nums:
        # 找到与 x 按位与为 0 的最大数字
        complement = u - 1 ^ x
        ans = max(ans, x * f[complement])
    
    return ans

# 测试代码
if __name__ == "__main__":
    nums = [64, 8, 32]
    result = maxProduct(nums)
    print(f"最大乘积: {result}")
    
    # 更多测试用例
    test_cases = [
        [1, 2, 3, 4, 5],
        [0, 0],
        [2, 3, 5, 7],
        [1, 1, 1, 1],
        [100, 200, 300],
    ]
    
    for i, test_nums in enumerate(test_cases):
        print(f"测试用例 {i+1}: {test_nums}")
        print(f"结果: {maxProduct(test_nums)}")
        print("-" * 30)

C++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
#include <climits>

using namespace std;

long long maxProduct(vector<int>& nums) {
    int max_val = *max_element(nums.begin(), nums.end());
    int w = 0;
    while (max_val > 0) {
        w++;
        max_val >>= 1;
    }
    int u = 1 << w;  // 2^w

    int n = nums.size();

    // 情况一：暴力枚举
    if (n * n <= u * w) {
        long long ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if ((nums[i] & nums[j]) == 0) {
                    ans = max(ans, (long long)nums[i] * nums[j]);
                }
            }
        }
        return ans;
    }

    // 情况二：SOS DP
    vector<int> f(u, 0);

    // 初始化 f
    for (int x : nums) {
        f[x] = x;
    }

    // SOS DP 求子集最大值
    for (int i = 0; i < w; i++) {
        for (int mask = 0; mask < u; mask++) {
            if (mask & (1 << i)) {
                f[mask] = max(f[mask], f[mask ^ (1 << i)]);
            }
        }
    }

    long long ans = 0;
    for (int x : nums) {
        int complement = (u - 1) ^ x;  // x 的按位补集
        ans = max(ans, (long long)x * f[complement]);
    }

    return ans;
}

int main() {
    vector<int> nums = {64, 8, 32};
    long long result = maxProduct(nums);
    cout << result << endl;
    return 0;
}