# 2939. 最大异或乘积

### 题目地址(2939. 最大异或乘积 - 力扣（LeetCode）)

<https://leetcode.cn/problems/maximum-xor-product/>

### 题目描述

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

由于答案可能会很大，返回它对 `109 + 7` **取余** 后的结果。

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

&#x20;

**示例 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) 的最大值。
```

&#x20;

**提示：**

* `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 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://p.ipic.vip/h9nm77.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/2939.maximum-xor-product.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.