1、按位异或运算 ^
按位异或（^）： 相同为0，不同为1；
按位异或（^）： 相当于无进位相加
例如：01010 ^ 01101 = 00111
特性：
- 任何数异或上0等于其本身： 0 ^ n = n
- 两个相同的数异或为0： n ^ n = 0
- 异或运算满足交换律，和结合律
- 交换：a ^ b = b ^ a
- 结合：(a ^ b) ^ c = a ^ (b ^ c)
3、常见 Coding
3.1、不使用额外变量交换两个数
注意：a,b 不能是同一个块内存，a,b不能指向同一个内存
示例：
a = 5，b = 6
a = 6，b = 5
步骤：
- a = a ^ b
- b = a ^ b，相当于 b = (a ^ b) ^ b = a
- a = a ^ b，相当于 a = (a ^ b) ^ a = b
代码实现：
点击查看代码
public class XorSwap {
public static void swap(int[] arr, int i, int j) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
public static void main(String[] args) {
int a = 5;
int b = 6;
System.out.println("a=" + a + ", b=" + b);
a = a ^ b;
b = a ^ b;
a = a ^ b;
System.out.println("a=" + a + ", b=" + b);
int[] arr = {3, 1, 100};
int i = 0;
int j = 0;
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
System.out.println("arr[i]=" + arr[i] + ", arr[j]=" + arr[j]);
// [0, 1, 100]
System.out.println(Arrays.toString(arr));
}
}
3.2、怎么把一个int类型的数，提取出最右侧的1来
操作： a 按位与 a 的相反数，a & (-a) = a & (~a + 1)
例：
a: 0010 1100
~a:1101 0011 // 取反
+1:1101 0100 // 取反加一，即 -a
a & (-a) = 0000 0100
3.3、数组arr[]中一种数出现了奇数次，其他都出现了偶数次，怎么找到并打印这种数？
分析： 异或相当于无进位相加，偶数个 1 相加为 0，奇数个 1 相加为 1
public static void printOddTimesNum(int[] arr) {
int eor = 0;
int len = arr.length;
for (int i = 0; i < len; i++) {
eor ^= arr[i];
}
System.out.println(eor);
}
3.4、数组arr[]中，有两种数，出现奇数次，其他出现偶数次，怎么找到并打印这两种数？
3.4.1、分析
- 假设 a,b出现奇数次，[..a,..,b..]
- 遍历异或arr 中所有数得到结果一定是： eor = a ^ b
- 将 eor最右侧的 1提取出来，则可以将arr 分为两堆数据 [{a...},{b...}]
- 遍历异或{a...} 这一堆数据结果即为： eor' = a
- 所以 b = eor ^ eor' = a ^ b ^ a
3.4.2、代码实现
点击查看代码
public class EvenTimesOddTimes {
/**
* arr中，有两种数，出现奇数次，其他出现偶数次
* 步骤：假设 a,b出现奇数次
* 遍历异或所有数，得到结果 eor = a ^ b != 0
*
* @param arr
*/
public static void printOddTimesNum2(int[] arr) {
int eor = 0;
int len = arr.length;
for (int i = 0; i < len; i++) {
eor ^= arr[i];
}
// 将eor 最右侧的 1 提取出来
// 例: eor: 0011 0100
// rightOne: 0000 0100
int rightOne = eor & (-eor);
// eor = a ^ b，则最右侧 1提取的数 rightOne, 就可以把 arr 分为两堆 [{a...},{b...}]
// ero', 假设 a 的最右侧 1，与 rightOne 相等，则用 eor' 异或 {a...} 这一堆数其结果就是 eor' = a
int eor_ = 0;
for (int i = 0; i < len; i++) {
if ((rightOne & arr[i]) != 0) {
eor_ ^= arr[i];
}
}
// eor = a ^ b，eor' = a，则 b = eor ^ eor'
System.out.println("a=" + eor_ + " b=" + (eor ^ eor_));
}
public static void main(String[] args) {
int[] arr = {3, 3, 2, 3, 1, 1, 1, 3, 1, 1, 1};
printOddTimesNum(arr); // 2
int[] arr1 = {3, 3, 2, 3, 1, 1, 5, 1, 3, 1, 1, 1};
printOddTimesNum2(arr1); // a=5 b=2
}
}
3.5、数组中所有的数都出现了M次，只有一种数出现了K次，返回出现了K次的数
- 输入 arr[] 一定能保证
- 数组中所有的数都出现了 M 次，只有一种数出现了 K 次
- 且 1 <= K < M
- 返回：出现了 K 次的数
- 要求：额外空间复杂度 O(1)，时间复杂度 O(N)
3.5.1、分析
- int 类型的数 4 字节 = 32 位，申请一个临时数组 temp[32]
- 将所有数的二进制位，出现 1 的次数保存到temp 中
- temp[0] 0位置的 1 出现了几次
- temp[i] i位置的 1 出现了几次
- 因为 K < M，所以如果某一位的 1 出现的次数不是 M 的整数倍，那么出现 K 次的数在该位置上一定为 1
3.5.2、代码实现，三种不同的实现方式
点击查看代码
/**
* 输入 arr[] 一定能保证
* 数组中所有的数都出现了 M 次，只有一种数出现了 K 次
* 且 1 <= K < M
* 返回：出现了 K 次的数
* 要求：额外空间复杂度 O(1)，时间复杂度 O(N)
*
* @author smile
*/
public class KM {
/**
* 数组中所有的数都出现了 M 次，只有一种数出现了 K 次
*
* @param arr 数组
* @param K 某个数出现了 k 次
* @param M 出现了 m 次的数
* @return 出现了 k 次的数
*/
public static int onlyKTimes(int[] arr, int K, int M) {
int[] temp = new int[32];
// temp[0] 0位置的 1 出现了几次
// temp[1] 1位置的 1 出现了几次
for (int num : arr) {
for (int i = 0; i <= 31; i++) {
temp[i] += (num >> i) & 1;
}
}
// K < M，如果某一位的 1 出现的次数不是 M 的整数倍，
// 那么出现 K 次的数在该位置上一定为 1
int res = 0;
for (int i = 0; i < 32; i++) {
if (temp[i] % M != 0) {
res |= (1 << i);
}
}
return res;
}
public static HashMap<Integer, Integer> maps = new HashMap<>();
public static int onlyKtimes1(int[] arr, int k, int m) {
if (maps.size() == 0) {
mapCreate(maps);
}
int[] temp = new int[32];
// temp[0] 0 位置的 1 出现了几次
// temp[i] i 位置的 1 出现了几次
for (int num : arr) {
while (num != 0) {
int rightOne = num & (-num);
temp[maps.get(rightOne)]++;
// 将 num 的最后一位 1 置 0
num ^= rightOne;
}
}
int res = 0;
for (int i = 0; i < 32; i++) {
if (temp[i] % m != 0) {
res |= (1 << i);
}
}
return res;
}
public static void mapCreate(HashMap<Integer, Integer> maps) {
int value = 1;
for (int i = 0; i < 32; i++) {
maps.put(value, i);
value <<= 1;
}
}
// 测试，哈希表统计的形式
public static int test(int[] arr, int K, int M) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int num : arr) {
if (map.containsKey(num)) {
map.put(num, map.get(num) + 1);
} else {
map.put(num, 1);
}
}
for (int num : map.keySet()) {
if (map.get(num) == K) {
return num;
}
}
return -1;
}
/**
* 生成满足条件，所有的数都出现了 M 次，只有一种数出现了 K 次，的数组
*
* @param maxKinds 数组中最多有几种数
* @param range 数组中每个数的范围 [-range, range]
* @param k 出现了 k 次
* @param m 出现了 m 次
* @return 新数组
*/
public static int[] generateRandomArray(int maxKinds, int range, int k, int m) {
// 先生成出现了 k 次的数
int kTimesNum = randomNumber(range);
int times = k;
// 数的种类，最少 2 种数
int numKinds = (int) (Math.random() * maxKinds) + 2;
// 数组长度: k * 1 + (numKinds - 1) * m
int[] arr = new int[k + (numKinds - 1) * m];
int index = 0;
for (; index < times; index++) {
arr[index] = kTimesNum;
}
// k 次的数加入之后，种类减 1
numKinds--;
HashSet<Integer> set = new HashSet<>();
set.add(kTimesNum);
// 设置出现 m 次的数
while (numKinds != 0) {
int curNum = 0;
do {
curNum = randomNumber(range);
} while (set.contains(curNum));
set.add(curNum);
numKinds--;
for (int i = 0; i < m; i++) {
arr[index++] = curNum;
}
}
// arr 已经生成，将其打乱
int len = arr.length;
for (int i = 0; i < len; i++) {
// i 位置的数，随机和 j 位置的数交换
// 0 ~ N - 1
int j = (int) (Math.random() * len);
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
return arr;
}
/**
* 生成 [-range, range] 范围的数
*
* @param range 整数
* @return 整数
*/
private static int randomNumber(int range) {
return (int) (Math.random() * (range + 1)) - (int) (Math.random() * (range + 1));
}
public static void main(String[] args) {
int[] arr = {1, 2, 2, 4, 2, 1, 1, 4};
int k = 2;
int m = 3;
// 4
System.out.println(onlyKTimes(arr, k, m));
int[] arr1 = {1, 2, 2, -1, 2, 1, 1, -1};
// -1
System.out.println(onlyKTimes(arr1, k, m));
// 测试 KM
int kinds = 5;
int range = 30;
int testTimes = 500;
int max = 9;
System.out.println("测试开始");
for (int i = 0; i < testTimes; i++) {
// 1 ~ 9
int a = (int) (Math.random() * max) + 1;
int b = (int) (Math.random() * max) + 1;
k = Math.min(a, b);
m = Math.max(a, b);
// 保证 k < m
if (k == m) {
m++;
}
int[] array = generateRandomArray(kinds, range, k, m);
int res1 = test(array, k, m);
int res2 = onlyKTimes(array, k, m);
int res3 = onlyKtimes1(array, k, m);
if (res1 != res2 || res2 != res3) {
System.out.println("出错了！");
System.out.println(res1);
System.out.println(res2);
System.out.println(res3);
break;
}
}
System.out.println("测试结束！");
}
}