> For the complete documentation index, see [llms.txt](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/2939.maximum-xor-product.md).
# 2939. 最大异或乘积
### 题目地址(2939. 最大异或乘积 - 力扣（LeetCode）)
### 题目描述
给你三个整数 `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 < 250`
* `0 <= n <= 50`
### 前置知识
* 位运算
### 公司
* 暂无
### 思路
题目是求 a xor x 和 b xor x 的乘积最大。x 的取值范围是 0 <= x < 2^n。为了方便这里我们 a xor x 记做 axorx，b xor x 记做 bxorx，
首先我们要注意。对于除了低 n 位，其他位不受 x 异或影响。因为 x 除了低 n 可能不是 1，其他位都是 0。而 0 与任何数异或还是自身，不会改变。
因此我们能改的只是低 n 位。那么 x 的低 n 位具体去多少才可以呢？
朴素地枚举每一位上是 0 还是 1 的时间复杂度是 $2^n$，无法通过。
我们不妨逐位考虑。对于每一位：
* 如果 a 和 b 在当前位相同， 那么 x 只要和其取相反的就行，异或答案就是 1。
* 如果 a 和 b 在当前位不同， 那么 axorx 在当前位的值与bxorx 在当前位的值吧必然一个是 0 一个是 1，那么让哪个是 1，哪个是 0 才能使得乘积最大么？
根据初中的知识，对于和相同的两个数，两者数相差的越小乘积越大。因此我们的策略就是 axorx 和 bxorx 哪个小就让他大一点，这样可以使得两者差更小。
那么没有最终计算出来 axorx 和 bxorx，怎么提前知道哪个大哪个小呢？其实我们可以从高位往低位遍历，这样不用具体算出来 axorx 和 bxorx 也能知道大小关系啦。
### 关键点
* 除了低 n 位，其他不受 x 异或影响
* 对于每一位，贪心地使得异或结果为 1， 如果不能，贪心地使较小的异或结果为 1
### Code
* 语言支持：Python3
Python3 Code:
```python
class Solution:
def maximumXorProduct(self, a: int, b: int, n: int) -> int:
axorx = (a >> n) << n # 低 n 位去掉，剩下的前 m 位就是答案中的 axorb 二进制位。剩下要做的是确定低 n 位具体是多少
bxorx = (b >> n) << n
MOD = 10 ** 9 + 7
for i in range(n-1, -1, -1):
t1 = a >> i & 1
t2 = b >> i & 1
if t1 == t2:
axorx |= 1 << i
bxorx |= 1 << i
else:
if axorx < bxorx:
axorx |= 1 << i # 和一定，两者相差越小，乘积越大
else:
bxorx |= 1 << i
axorx %= MOD
bxorx %= MOD
return (axorx * bxorx) % MOD
```
**复杂度分析**
* 时间复杂度：$O(n)$
* 空间复杂度：$O(1)$
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
