异或-java-leetcode
1486.数组异或操作
给你两个整数，
n和start。数组
nums定义为：nums[i] = start + 2*i（下标从 0 开始）且n == nums.length。请返回
nums中所有元素按位异或（XOR）后得到的结果。示例 1：
输入：n = 5, start = 0 输出：8 解释：数组 nums 为 [0, 2, 4, 6, 8]，其中 (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8 。 "^" 为按位异或 XOR 运算符。示例 2：
输入：n = 4, start = 3 输出：8 解释：数组 nums 为 [3, 5, 7, 9]，其中 (3 ^ 5 ^ 7 ^ 9) = 8.示例 3：
输入：n = 1, start = 7 输出：7示例 4：
输入：n = 10, start = 5 输出：2提示：
1 <= n <= 10000 <= start <= 1000n == nums.length
原理
同一数字异或两次结果为 0，任意数字与 0 异或结果为其本身。题目要求对生成的数组
nums[i] = start + 2 * i的所有元素进行异或，因此无需实际创建数组，而是通过累加生成每个元素的值并逐步异或累计结果。循环中，每次计算新元素（temp += 2）后，与当前累计值进行异或（start = start ^ temp），最终返回所有元素异或后的结果。这种方法高效地模拟了异或操作，避免了数组的显式存储。
代码
class Solution {
public int xorOperation(int n, int start) {
// 使用临时变量 temp 初始化为 start，用于生成数组中的元素
int temp = start;
// 遍历从 1 到 n-1 的索引，依次计算异或值
for (int i = 1; i < n; i++) {
// temp 累加 2，生成下一个数组元素
temp += 2;
// 将当前 start 与新的 temp 按位异或，更新 start 的值
start = start ^ temp;
}
// 返回最终计算出的异或结果
return start;
}
}
2429.最小异或
给你两个正整数
num1和num2，找出满足下述条件的正整数x：
x的置位数和num2相同，且x XOR num1的值 最小注意
XOR是按位异或运算。返回整数
x。题目保证，对于生成的测试用例，x是 唯一确定 的。整数的 置位数 是其二进制表示中
1的数目。示例 1：
输入：num1 = 3, num2 = 5 输出：3 解释： num1 和 num2 的二进制表示分别是 0011 和 0101 。 整数 3 的置位数与 num2 相同，且3 XOR 3 = 0是最小的。示例 2：
输入：num1 = 1, num2 = 12 输出：3 解释： num1 和 num2 的二进制表示分别是 0001 和 1100 。 整数 3 的置位数与 num2 相同，且3 XOR 1 = 2是最小的。提示：
1 <= num1, num2 <= 109
原理
- 统计目标置位数：通过对
num2的二进制逐位遍历，统计其 1 的数量，记录为count。- 构造结果的高效二进制形式：优先使用
num1的高位 1 填充结果，如果num1的 1 不够，则从低位补充 0 为 1，直到置位数满足要求。- 二进制转十进制：将构造的二进制数转为十进制输出。
最终，结果
x的置位数与num2相同，且尽量与num1的高位对齐，使得x XOR num1的结果最小。
代码
class minimizeXorSolution {
public int minimizeXor(int num1, int num2) {
int x = 0; // 用于保存最终结果
int count = 0; // 记录 num2 中二进制 1 的数量
// 计算 num2 的二进制中 1 的数量
while (num2 != 0) {
if (num2 % 2 == 1) {
count++; // 统计置位数
}
num2 /= 2; // 右移一位
}
// 将 num1 的二进制每一位存入数组 arr 中
int[] arr = new int[30]; // 假设最大处理 30 位
int num11 = num1, index = 0;
while (num11 != 0) {
if (num11 % 2 == 1) {
arr[index] = 1; // 保存二进制的每一位
}
num11 /= 2; // 右移一位
index++;
}
// 根据 num1 和 count 构造结果的二进制形式
int[] arr1 = new int[30]; // 构造结果的二进制形式
for (int i = 29; i >= 0; i--) {
if (arr[i] == 1) { // 优先利用 num1 的高位 1
arr1[i] = 1;
count--;
if (count == 0) { // 如果满足置位数要求
int temp = 1;
for (int j = 0; j < 30; j++) {
x += (temp * arr1[j]); // 转换二进制为十进制
temp *= 2;
}
return x;
}
}
}
// 如果高位 1 不够，补充低位 0 为 1
for (int i = 0; i <= 29; i++) {
if (arr[i] == 0) {
arr1[i] = 1; // 设置低位 1
count--;
}
if (count == 0) { // 如果满足置位数要求
int temp = 1;
for (int j = 0; j < 30; j++) {
x += (temp * arr1[j]); // 转换二进制为十进制
temp *= 2;
}
return x;
}
}
return 0; // 默认返回值（理论上不会到这里）
}
}
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
原理
这段代码的核心是通过构造一个满足条件的整数
x，使得(a XOR x) * (b XOR x)的结果最大化。构造x的方式如下：
- 将 a 和 b 转为二进制数组：用数组存储二进制形式，方便逐位操作。
- 根据 XOR 特性选择 x 的每一位：
- 如果
a[i]和b[i]都为 0，则选择x[i] = 1。- 如果
a[i]和b[i]都为 1，则选择x[i] = 0。- 如果两者不同，则选择贡献最大的那个（优先最大化乘积）。
- 从低到高处理 n 位：仅处理低
n位，确保不超出范围。- 计算结果：逐位还原
x，并计算(a XOR x)和(b XOR x)，取模后返回结果。该方法利用了 XOR 操作的对称性和二进制特性，在最大化乘积的同时保证计算效率。
代码
import java.util.Scanner;
class maximumXorProductSolution {
public static int maximumXorProduct(long a, long b, int n) {
// 定义变量
long x = 0; // 存储 x 的值（不直接用）
long a1 = a, b1 = b; // 临时保存 a 和 b
long sumA = 0, sumB = 0; // 存储 (a XOR x) 和 (b XOR x) 的十进制值
long XA = 0, XB = 0; // 累计 (a XOR x) 和 (b XOR x) 的临时值
int[] arrayA = new int[50]; // 保存 a 的二进制表示
int[] arrayB = new int[50]; // 保存 b 的二进制表示
int[] arrayX = new int[50]; // 保存构造的 x 的二进制表示
int countA = 0, countB = 0; // 用于保存 a 和 b 的有效位数
// 将 a 的二进制表示存入 arrayA 数组
while (a1 != 0) {
if (a1 % 2 == 1) {
arrayA[countA++] = 1;
} else {
arrayA[countA++] = 0;
}
a1 /= 2; // 右移一位
}
// 将 b 的二进制表示存入 arrayB 数组
while (b1 != 0) {
if (b1 % 2 == 1) {
arrayB[countB++] = 1;
} else {
arrayB[countB++] = 0;
}
b1 /= 2; // 右移一位
}
// 计算 2^(n-1) 的初始值，用于二进制计算
long temp = 1;
for (int i = 1; i < 50; i++) {
temp *= 2;
}
// 构造 x 的二进制表示，优先选择最大化结果
for (int i = 49; i >= 0; i--) {
if (i < n) { // 仅处理低 n 位
if (arrayA[i] == 0 && arrayB[i] == 0) {
arrayX[i] = 1; // 都为 0，选择 1 以最大化乘积
} else if (arrayA[i] == 1 && arrayB[i] == 1) {
arrayX[i] = 0; // 都为 1，选择 0 避免冲突
} else {
// 如果两者不相同，选择 a 和 b 中较大贡献的位
if (XA > XB) {
arrayX[i] = arrayA[i];
} else {
arrayX[i] = arrayB[i];
}
}
}
// 更新 XOR 值
XA += temp * (arrayX[i] ^ arrayA[i]);
XB += temp * (arrayX[i] ^ arrayB[i]);
temp /= 2;
}
// 根据构造的 x 计算最终的 XOR 值
temp = 1;
for (int i = 0; i < 50; i++) {
if (arrayA[i] != arrayX[i]) {
sumA += temp;
}
if (arrayB[i] != arrayX[i]) {
sumB += temp;
}
temp *= 2;
}
// 计算最终答案，取模防止溢出
long answer = (sumA % 1000000007) * (sumB % 1000000007) % 1000000007;
return (int) answer;
}
}
810.黑板异或游戏
黑板上写着一个非负整数数组
nums[i]。Alice 和 Bob 轮流从黑板上擦掉一个数字，Alice 先手。如果擦除一个数字后，剩余的所有数字按位异或运算得出的结果等于
0的话，当前玩家游戏失败。 另外，如果只剩一个数字，按位异或运算得到它本身；如果无数字剩余，按位异或运算结果为0。并且，轮到某个玩家时，如果当前黑板上所有数字按位异或运算结果等于
0，这个玩家获胜。假设两个玩家每步都使用最优解，当且仅当 Alice 获胜时返回
true。示例 1：
输入: nums = [1,1,2] 输出: false 解释: Alice 有两个选择: 擦掉数字 1 或 2。 如果擦掉 1, 数组变成 [1, 2]。剩余数字按位异或得到 1 XOR 2 = 3。那么 Bob 可以擦掉任意数字，因为 Alice 会成为擦掉最后一个数字的人，她总是会输。 如果 Alice 擦掉 2，那么数组变成[1, 1]。剩余数字按位异或得到 1 XOR 1 = 0。Alice 仍然会输掉游戏。示例 2:
输入: nums = [0,1] 输出: true示例 3:
输入: nums = [1,2,3] 输出: true提示：
1 <= nums.length <= 10000 <= nums[i] < 216
原理
在这个游戏中，Alice 和 Bob 轮流擦除一个数字，直到剩下的数字按位异或运算结果为零，当前玩家失败。玩家的目标是让对方陷入一个局面，在该局面中对方无法避免让剩余数字的异或结果为零。为了找到最优解，代码通过计算整个数组的按位异或值（
ans），并根据数组长度的奇偶性来判断最终结果。
- 异或特性：异或运算具有自反性和交换性，因此整个数组的异或结果可以决定游戏的最终状态。
- 偶数长度数组：如果异或结果为零，Alice 不能获胜，因为无论她如何选择，最终 Bob 会强制让异或结果为零，因此 Alice 输。如果异或结果不为零，Alice 可以通过最优选择获胜。
- 奇数长度数组：如果异或结果为零，Alice 直接获胜，因为这意味着当前的局面就是 Alice 所期望的目标。如果异或结果不为零，则 Alice 输，因为她无法避免最终的结果。
因此，最终的判断依据是整个数组的异或值以及数组的长度是否为偶数或奇数。
代码
class xorGameSolution {
public static boolean xorGame(int[] nums) {
// 初始化 ans 为数组的第一个元素
int ans = nums[0];
// 对数组的每个元素进行按位异或操作
for (int i = 1; i < nums.length; i++) {
ans = ans ^ nums[i]; // 更新 ans 为当前 ans 和 nums[i] 的异或结果
System.out.println("第 " + i + ": " + ans); // 输出当前异或值，用于调试
}
// 如果数组长度是偶数
if (nums.length % 2 == 0) {
// 如果最终的异或结果为 0，Alice 输；否则 Alice 赢
if (ans == 0) {
System.out.println(ans); // 输出最终的异或值，用于调试
return false; // Bob 胜利
} else {
return true; // Alice 胜利
}
}
// 如果数组长度是奇数
else {
// 如果最终的异或结果为 0，Alice 赢；否则 Alice 输
if (ans == 0) {
return true; // Alice 胜利
} else {
return false; // Bob 胜利
}
}
}
}