最大异或乘积

难度: Medium

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

由于答案可能会很大，返回它对 10⁹+ 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 < 2ⁿ中 (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 < 2ⁿ中 (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 < 2ⁿ中 (a XOR x) * (b XOR x) 的最大值。

提示：

0 <= a, b < 2⁵⁰
0 <= n <= 50

Submission

运行时间: 24 ms

内存: 16.8 MB

class Solution:
    def maximumXorProduct(self, a: int, b: int, n: int) -> int:
        if a < b:
            a, b = b, a 
        mask = (1 << n) - 1 
        ax, ay, bx, by = a & ~mask, a & mask, b & ~mask, b & mask 
        left = ay ^ by 
        one = mask ^ left 
        ax |= one 
        bx |= one 
        if left > 0 and ax == bx:
            high = 1 << (left.bit_length() - 1)
            ax |= high 
            left ^= high 
        bx |= left 
        return ax * bx % (10 ** 9 + 7)

Explain

此题解通过利用位运算的特性来优化找到最大乘积的过程。首先，确保a不小于b，以简化后续操作。接着，定义一个mask来限制x的范围（确保x小于2^n）。将a和b分别与mask的补码（~mask）和mask本身进行AND操作，得到高位部分（ax, bx）和低位部分（ay, by）。计算ay和by的异或（XOR）结果left，它代表a和b在mask范围内的差异位。接下来，计算一个值one，它是mask与left的异或结果，用于将ax和bx调整到尽可能大的值以获得较大的乘积。在调整过程中，如果left不为0且ax与bx相等，还会进一步调整ax和bx，以确保它们能取到可能的最大值。最后，计算ax与bx的乘积，并取模10^9+7得到结果。

时间复杂度: O(1)

空间复杂度: O(1)

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  # 创建一个位掩码以限制x的大小
        ax, ay, bx, by = a & ~mask, a & mask, b & ~mask, b & mask  # 分割a和b为高位和低位部分
        left = ay ^ by  # 计算低位部分的异或，找出差异位
        one = mask ^ left  # 计算一个值来调整ax和bx到较大值
        ax |= one  # 更新ax
        bx |= one  # 更新bx
        if left > 0 and ax == bx:
            high = 1 << (left.bit_length() - 1)
            ax |= high  # 在需要时进一步调整ax和bx
            left ^= high
        bx |= left  # 最终确定bx的值
        return ax * bx % (10 ** 9 + 7)  # 计算结果并取模

Explore

确保a不小于b是为了减少算法中的条件判断，从而简化程序的逻辑。由于乘法操作是交换性的（即a*b与b*a的结果相同），选择较大的数作为a可以减少在后续处理中的分支判断，尤其是在涉及位运算优化时，这种处理可以保持一致性，使得代码更加简洁和高效。

在题解中，mask是通过表达式`(1 << n) - 1`计算得到的。这个表达式得到的结果是一个二进制数，其中从最低位到第n位都是1，其余位都是0。这样的掩码用于通过与操作（AND）限制整数的位数。当`a & mask`或`b & mask`执行时，这个操作保留了整数的最低n位，而将高于n的位都置为0。因此，这保证了不管a或b的实际大小如何，通过mask处理后的结果都不会超过2^n-1，从而确保x的值在指定的位范围内。

将a和b分割为高位和低位部分的主要目的是为了分别处理，从而在位运算中实现更细致的控制和优化。通过这种分割，可以独立地优化a和b的低位部分（通过异或操作找出差异位），同时保留高位部分的信息。这样的分割使得算法可以在不同的位级别上调整数值，以求得最大的乘积结果。此外，这种方式也便于实现基于位操作的优化策略，如进一步调整和对齐位以增大乘积值。

变量one在算法中的作用是用于调整ax和bx，使其尽可能大，以获得更大的乘积结果。one的计算方法是`mask ^ left`，其中left是ay和by的异或结果，代表了a和b在低位的差异位。通过将mask与left异或，one的结果中的1位代表了在ax和bx中需要设置为1的位，以使这两个数尽可能大。因此，`ax |= one`和`bx |= one`的操作确保了在不改变已有的差异位的情况下，尽可能将ax和bx的其他位也设置为1，从而使得最终的乘积最大化。