最大异或乘积

Given three integers a, b, and n, return the maximum value of (a XOR x) * (b XOR x) where 0 <= x < 2n.

Since the answer may be too large, return it modulo 109 + 7.

Note that XOR is the bitwise XOR operation.

 

Example 1:

Input: a = 12, b = 5, n = 4
Output: 98
Explanation: For x = 2, (a XOR x) = 14 and (b XOR x) = 7. Hence, (a XOR x) * (b XOR x) = 98. 
It can be shown that 98 is the maximum value of (a XOR x) * (b XOR x) for all 0 <= x < 2n.

Example 2:

Input: a = 6, b = 7 , n = 5
Output: 930
Explanation: For x = 25, (a XOR x) = 31 and (b XOR x) = 30. Hence, (a XOR x) * (b XOR x) = 930.
It can be shown that 930 is the maximum value of (a XOR x) * (b XOR x) for all 0 <= x < 2n.

Example 3:

Input: a = 1, b = 6, n = 3
Output: 12
Explanation: For x = 5, (a XOR x) = 4 and (b XOR x) = 3. Hence, (a XOR x) * (b XOR x) = 12.
It can be shown that 12 is the maximum value of (a XOR x) * (b XOR x) for all 0 <= x < 2n.

 

Constraints:

• 0 <= a, b < 250
• 0 <= n <= 50

/*
  思路：
  1. 使用 Java Stream API 实现相同的逻辑。
  2. 利用 IntStream.rangeClosed 生成 x 的范围 0 <= x < 2^n。
  3. 对每个 x 计算 (a XOR x) * (b XOR x)，并取模 10^9 + 7。
  4. 返回这些计算结果中的最大值。
*/

import java.util.stream.IntStream;

public class Solution {
    public int maxProduct(int a, int b, int n) {
        int maxX = (1 << n) - 1; // 2^n - 1
        int MOD = 1000000007;
        return IntStream.rangeClosed(0, maxX)
                .mapToLong(x -> ((long)(a ^ x) * (long)(b ^ x)) % MOD)
                .max()
                .orElse(0);
    }
}

此题解通过利用位运算的特性来优化找到最大乘积的过程。首先，确保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)