Microsoft OA XOR 乘积最大化：共同位填 1、差异位平衡

题目重点：在 X<2^N 下最大化 (A xor X)(B xor X)，逐位构造两个结果，解释大位优先与取模时机。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

按题目约束 A、B 是 N 位以内的非负整数，N≥1 才可能满足 1≤A,B<2^N。
目标先在整数域最大化真实乘积，最后才对 MOD 取模；不能在比较候选时用取模后的大小。
X 各位可独立取 0/1，没有额外置位数限制。

解题路线

记 U=A xor X、V=B xor X。对 A/B 同值的位，可以选择 X 使 U/V 该位都为 1；两者同时增加，非负乘积不会变差。
对 A/B 不同的位，U/V 恰好一边得到该位的 1，二者的总和在所有差异位选择间固定。因此乘积最大化等价于让 U 与 V 尽可能接近。
从高位到低位处理差异位，将当前高位前缀较小的一边补上该位；高位权重大于所有剩余低位权重总和，先平衡最高未定差异位不会被之后反转。
构造完整的 U、V 后计算 U×V，再做一次 MOD；N≤30 时两数各小于 2^30，乘积可达约 2^60，需在固定宽度语言用 64 位或大整数。

手动走一遍

A=1(01₂)、B=2(10₂)、N=2，两位均不同。先将高位 2 给 U，再将低位 1 给 V，得到 U=2、V=1，乘积 2；相反分配也得 2。若 A/B 某位同为 0，选 X 该位为 1 使两个结果同时升高。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

MOD = 1_000_000_007


def maximum_xor_product(a: int, b: int, width: int) -> int:
    """Maximize (a xor x)*(b xor x) for 0 <= x < 2**width."""
    if width < 0 or a < 0 or b < 0 or a >= 1 << width or b >= 1 << width:
        raise ValueError("input outside bit width")
    left = right = 0
    for bit in range(width - 1, -1, -1):
        mask = 1 << bit
        a_bit = bool(a & mask)
        b_bit = bool(b & mask)
        if a_bit == b_bit:
            left |= mask
            right |= mask
        elif left <= right:
            left |= mask
        else:
            right |= mask
    return (left * right) % MOD


if __name__ == "__main__":
    assert maximum_xor_product(1, 2, 2) == 2

复杂度

扫描 N 位，O(N) 时间、O(1) 额外空间。Python 大整数乘法对 N≤30 可视为常数规模；一般任意精度位宽需计入大整数乘法成本。

易错点与追问

容易失分的边界

只求 X 或只求两个 XOR 结果的最大值，忽略乘积需要平衡。
先对中间结果取模再比较乘积，模序不保留原大小。
差异位从低到高贪心，低位决策无法确保高位平衡。
漏看 N=0 与 A≥1 约束冲突。
在 32 位有符号整数里直接相乘导致溢出。

继续深挖

若 A/B 有 N 位以外的固定高位，平衡决策如何纳入不可修改前缀？
如果 X 的置位数恰为 k，独立逐位贪心为何失效？
能否返回一个满足最大乘积且最小的 X？