class Solution {
public:
int maximumXorProduct(long long a, long long b, int n) {
}
};
2939. 最大异或乘积
给你三个整数 a ，b 和 n ，请你返回 (a XOR x) * (b XOR x) 的 最大值 且 x 需要满足 0 <= x < 2n。
由于答案可能会很大，返回它对 109 + 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 < 2500 <= n <= 50原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 2.3 MB, 提交时间: 2023-11-21 21:38:52
func maximumXorProduct(A, B int64, n int) int {
const mod = 1_000_000_007
a, b := int(A), int(B)
if a < b {
a, b = b, a // 保证 a >= b
}
mask := 1<<n - 1
ax := a &^ mask // 第 n 位及其左边，无法被 x 影响，先算出来
bx := b &^ mask
a &= mask // 低于第 n 位，能被 x 影响
b &= mask
left := a ^ b // 可分配：a XOR x 和 b XOR x 一个是 1 另一个是 0
one := mask ^ left // 无需分配：a XOR x 和 b XOR x 均为 1
ax |= one // 先加到异或结果中
bx |= one
// 现在要把 left 分配到 ax 和 bx 中
// 根据基本不等式（均值定理），分配后应当使 ax 和 bx 尽量接近，乘积才能尽量大
if left > 0 && ax == bx { // a &^ mask = b &^ mask
// 尽量均匀分配，例如把 1111 分成 1000 和 0111
highBit := 1 << (bits.Len(uint(left)) - 1)
ax |= highBit
left ^= highBit
}
// 如果 a &^ mask 更大，则应当全部分给 bx（注意最上面保证了 a>=b）
bx |= left
return ax % mod * (bx % mod) % mod
}
cpp 解法, 执行用时: 0 ms, 内存消耗: 6.1 MB, 提交时间: 2023-11-21 21:38:23
class Solution {
public:
int maximumXorProduct(long long a, long long b, int n) {
if (a < b) {
swap(a, b); // 保证 a >= b
}
long long mask = (1LL << n) - 1;
long long ax = a & ~mask; // 第 n 位及其左边，无法被 x 影响，先算出来
long long bx = b & ~mask;
a &= mask; // 低于第 n 位，能被 x 影响
b &= mask;
long long left = a ^ b; // 可分配：a XOR x 和 b XOR x 一个是 1 另一个是 0
long long one = mask ^ left; // 无需分配：a XOR x 和 b XOR x 均为 1
ax |= one; // 先加到异或结果中
bx |= one;
// 现在要把 left 分配到 ax 和 bx 中
// 根据基本不等式（均值定理），分配后应当使 ax 和 bx 尽量接近，乘积才能尽量大
if (left > 0 && ax == bx) {
// 尽量均匀分配，例如把 1111 分成 1000 和 0111
long long high_bit = 1LL << (63 - __builtin_clzll(left));
ax |= high_bit;
left ^= high_bit;
}
// 如果 a & ~mask 更大，则应当全部分给 bx（注意最上面保证了 a>=b）
bx |= left;
const long long MOD = 1'000'000'007;
return ax % MOD * (bx % MOD) % MOD; // 注意不能直接 LL * LL，否则溢出
}
};
java 解法, 执行用时: 1 ms, 内存消耗: 39.1 MB, 提交时间: 2023-11-21 21:37:56
class Solution {
public int maximumXorProduct(long a, long b, int n) {
if (a < b) {
// 保证 a >= b
long temp = a;
a = b;
b = temp;
}
long mask = (1L << n) - 1;
long ax = a & ~mask; // 第 n 位及其左边，无法被 x 影响，先算出来
long bx = b & ~mask;
a &= mask; // 低于第 n 位，能被 x 影响
b &= mask;
long left = a ^ b; // 可分配：a XOR x 和 b XOR x 一个是 1 另一个是 0
long one = mask ^ left; // 无需分配：a XOR x 和 b XOR x 均为 1
ax |= one; // 先加到异或结果中
bx |= one;
// 现在要把 left 分配到 ax 和 bx 中
// 根据基本不等式（均值定理），分配后应当使 ax 和 bx 尽量接近，乘积才能尽量大
if (left > 0 && ax == bx) {
// 尽量均匀分配，例如把 1111 分成 1000 和 0111
long highBit = 1L << (63 - Long.numberOfLeadingZeros(left));
ax |= highBit;
left ^= highBit;
}
// 如果 a & ~mask 更大，则应当全部分给 bx（注意最上面保证了 a>=b）
bx |= left;
final long MOD = 1_000_000_007;
return (int) (ax % MOD * (bx % MOD) % MOD); // 注意不能直接 long * long，否则溢出
}
}
python3 解法, 执行用时: 32 ms, 内存消耗: 16.1 MB, 提交时间: 2023-11-21 21:37:28
class Solution:
def maximumXorProduct(self, a: int, b: int, n: int) -> int:
if a < b:
a, b = b, a # 保证 a >= b
mask = (1 << n) - 1
ax = a & ~mask # 第 n 位及其左边，无法被 x 影响，先算出来
bx = b & ~mask
a &= mask # 低于第 n 位，能被 x 影响
b &= mask
left = a ^ b # 可分配：a XOR x 和 b XOR x 一个是 1 另一个是 0
one = mask ^ left # 无需分配：a XOR x 和 b XOR x 均为 1
ax |= one # 先加到异或结果中
bx |= one
# 现在要把 left 分配到 ax 和 bx 中
# 根据基本不等式（均值定理），分配后应当使 ax 和 bx 尽量接近，乘积才能尽量大
if left > 0 and ax == bx:
# 尽量均匀分配，例如把 1111 分成 1000 和 0111
high_bit = 1 << (left.bit_length() - 1)
ax |= high_bit
left ^= high_bit
# 如果 a & ~mask 更大，则应当全部分给 bx（注意最上面保证了 a>=b）
bx |= left
return ax * bx % 1_000_000_007