2026-02-02：没有公共位的整数最大乘积。用go语言，给定一个整数数组 nums，选出两个不同位置的元素（下标不同），要求这两个数在二进制

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)
                }
            }
        }
        returnint64(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])
    }
    returnint64(ans)
}

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

# -*-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)

#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;
    return0;
}