最大异或乘积

题目

2939. 最大异或乘积

---

给你三个整数 a ，b 和 n ，请你返回 (a XOR x) * (b XOR x) 的 最大值 且 x 需要满足 0 <= x < 2^n。

由于答案可能会很大，返回它对 10^9 + 7 取余 后的结果。

注意，XOR 是按位异或操作。

示例 1：

输入：a = 12, b = 5, n = 4
输出：98
解释：当 x = 2 时，(a XOR x) = 14 且 (b XOR x) = 7 。所以，(a XOR x) * (b XOR x) = 98 。
98 是所有满足 0 <= x < 2n 中 (a XOR x) * (b XOR x) 的最大值。

示例 2：

输入：a = 6, b = 7 , n = 5
输出：930
解释：当 x = 25 时，(a XOR x) = 31 且 (b XOR x) = 30 。所以，(a XOR x) * (b XOR x) = 930 。
930 是所有满足 0 <= x < 2n 中 (a XOR x) * (b XOR x) 的最大值。

示例 3：

输入：a = 1, b = 6, n = 3
输出：12
解释： 当 x = 5 时，(a XOR x) = 4 且 (b XOR x) = 3 。所以，(a XOR x) * (b XOR x) = 12 。
12 是所有满足 0 <= x < 2n 中 (a XOR x) * (b XOR x) 的最大值。

提示：

• 0 <= a, b < 2^50
• 0 <= n <= 50

题解

方法一：

思路

设$v_i$是十进制数v的二进制低位第i位。

我们可以修改a和b的低n位，当$i < n$时，若$a_i=b_i$我们可以都置为1以便乘积最大。若$a_i\ne b_i$我们必须也只能选择$a_i$或$b_i$中的一个置为1，另一个置为0。对于第二种情况我们应该让谁置为1呢？

我们让两个数u和v中选一个数增大t，求最大乘积。若$(u+t)v>u(v+t)$，则$v>u$，显然我们应该将t分配给u和v中较小的一个才能使得乘积更大。

设x为a为低n位置0后的结果，y为b低n位置0后的结果。

在这低n位中，我们从高位开始贪心，对于第i位:

• 当$a_i=b_i$，让$x_i=y_i=1$
• 当$a_i\ne b_i$
  • 对于当前$x > y$，让$y_i=1$
  • 对于当前$x < y$，让$x_i=1$

那么为什么要从高位开始呢？
如果最开始给其中一个数分配了1比特，剩余的比特位之和不及这个高位的比特位，所以剩余的将分给另一个数。

代码

class Solution {
public:
    using ll = long long;
    const ll MOD = 1e9+7;
    int maximumXorProduct(long long a, long long b, int n) {
        ll x = (a>>n)<<n, y = (b>>n)<<n;
        for (int i=n-1; i>=0; i--) {
            int u = a>>i&1, v = b>>i&1;
            if (u != v) {
                if (x<y) x |= 1LL<<i;
                else  y |= 1LL<<i;
            } else {
                x |= 1LL<<i;
                y |= 1LL<<i;
            }
        }
        return (x%MOD)*(y%MOD)%MOD;
    }
};