如何降低三整数XOR操作求和最大值代码的时间复杂度？

给定三个整数A、B、C，允许执行任意次数（含零次）以下操作：选择任意整数X满足X ≤ max(A,B,C)，将A替换为A^{X、B替换为B}X、C替换为C^X（其中^表示按位异或操作）。需找出A+B+C的最大可能值。

用户提供的Python代码如下：

A=2
B=2
C=2
def maxSum(a,b,c):
    list=[]
    l=[a,b,c]
    l.sort()
    if a==b==c:
        for x in range(int(a/2),l[-1]):
            new=((a^x)+(b^x)+(c^x))
            list.append(new)
        return list[-1]
    else:
        for x in range(l[1],l[-1]):
            new=((a^x)+(b^x)+(c^x))
            list.append(new)
        return list[-1]
maximum=maxSum(A,B,C)
print(maximum)

用户反馈该代码使用循环实现时运行耗时过长，希望了解如何降低代码的时间复杂度，以及需要进行哪些修改。

• 时间复杂度极高：当输入数值达到10^9级别时，循环遍历的范围会变得极大，时间复杂度直接变为O(N)，完全无法高效运行。
• 遍历范围无逻辑支撑：代码中选择的循环区间（a/2到最大值、l[1]到最大值）没有依据，可能漏掉能产生更大总和的X值，同时做了大量无效计算。
• 逻辑不完整：未考虑X=0（零次操作）的情况，也未验证区间外的X是否能得到更优解。

异或操作的每一位是独立影响结果的，我们可以从最高位到最低位依次判断，是否将X的该位设为1能让总和更大，同时保证最终X不超过三个数的最大值。这种方法的时间复杂度为O(31)（覆盖32位整数的有效位范围），几乎可以忽略不计。

具体步骤：

1. 初始化最优X为0，记录当前三个数的初始总和（对应X=0的情况）。
2. 从最高位（第30位）到最低位（第0位）依次处理：
   • 假设将当前位设为1，得到临时X候选值temp_x = best_x | (1 << bit)。
   • 若temp_x超过max(A,B,C)，则跳过该位（不满足操作限制）。
   • 计算三个数分别与temp_x异或后的总和，若该总和大于当前最优总和，则更新best_x和最优总和。
3. 最终返回最优总和即可。

def max_sum(a, b, c):
    max_val = max(a, b, c)
    best_x = 0
    current_max = a + b + c  # 初始为X=0的总和
    
    # 遍历32位整数的所有有效位（从最高位到最低位）
    for bit in range(30, -1, -1):
        temp_x = best_x | (1 << bit)
        if temp_x > max_val:
            continue  # 不满足X<=max_val的限制，跳过当前位
        # 计算异或后的总和
        new_sum = (a ^ temp_x) + (b ^ temp_x) + (c ^ temp_x)
        if new_sum > current_max:
            current_max = new_sum
            best_x = temp_x
    return current_max

# 测试示例
A = 2
B = 2
C = 2
print(max_sum(A, B, C))  # 输出9，对应X=1时的总和：3+3+3=9

内容的提问来源于stack exchange，提问作者Rutwik Patil