异和异或
认识异或
int a = 7;
// 此时a的二进制是 0111
int b = 13;
// 此时b的二进制是 1101
那么此刻我们把 a 异或 b 会的到 10
0 1 1 1
1 1 0 1
-------
1 0 1 0
官方点来说是 相同为0 不同为1
简单来记 就是直接想加 不用进位
和同或运算进行分开
异或性质
那么由此我们可以延伸出几个性质
- 0 ^ N = N ：0异或任何数 等于本身
- N ^ N = 0 ：数异或本身等于0
- a ^ b = b ^ a
- ( a ^ b ) ^ c = a ^ ( b ^ c )
- 同样一批数，不管是什么样的运算顺序，结果一定是一个数
异或题目
交换两个数
//通常我们以前交换两个数字是需要中间变量的
int a = 1;
int b = 2;
int c = 0;
c = a; // 1
a = b; // 2
b = c; // 1
我们学会异或以后，只需要通过三行代码就可以改变两个数，也不需要第三变量
// 为了方便记忆和理解
a = A;
b = B;
a = a ^ b;
b = a ^ b;
a = a ^ b;
那么此时我们来分析一下过程
- a = a ^ b; 因为是对a的赋值操作 此刻 a = A ^ B; b = B
- b = a ^ b; 对b的赋值操作，所以a不变；a = A ^ B; b = A ^ B ^ B; 在异或性质中我们知道，B^B=0，所以现在b = A ^ 0，一个数异或0等于本身，所以b = A;
- a = a ^ b = A ^ B ^ A = B，此时我们完成了交换AB的算法
一个数组中出现了奇数次的数
解题思路：
准备一个变量叫eor为0，让eor ^ 数组中的每个数，然后返回eor就是出现了奇数次的数
解题原理：
比如我们有数组nums，值为1111222233334（为了方便提前排好序了），你拿一个eor为0去异或他们，是不是偶数的都可以消掉了，然后最后实际上你留下来的就是eor ^ 4，因为eor默认是0，所以结果也就是eor = 4
代码演示：
剑指 Offer II 070. 排序数组中只出现一次的数字
136.只出现一次的数字
class Solution {
public int singleNonDuplicate(int[] nums) {
int eor = 0;
for(int i=0; i<nums.length; i++){
eor = eor ^ nums[i];
}
return eor;
}
}
提取整形数最右侧的1
题目描述：
a = 01101110010000
ans = 0000000010000
解题思路：
a & ~a+1
a = 01101110010000
~a = 10010001101111
~a+1 = 10010001110000 +1其实是为了让在～a这一步骤变0的最右侧1再变回来
a&~a+1 = 0000000010000
a&~a+1 == a & -a ，一个数取反+1 = 这个数的相反数
数组中出现奇数次的两个数
剑指 Offer 56 - I. 数组中数字出现的次数
解题思路：
首先我们还是准备一个变量eor，那么假设这个数组是nums：{1,1,2,3,4,4,5,5}，首先我们用eor数组中的每一位，那么出现偶数次的都可以被消除掉，最后eor=23，然后我们此刻 算出eor的二进制结果是
2 : 0 0 1 0
3 : 0 0 1 1
res ：0 0 0 1
此时我们取最右边的1，因为这个1可以分开我们所获取的这两个数，然后此时我们有个变量叫res，首先通过上面 提取整形数最右侧的1 这个方法，把数组中所有的数字，判断一下最右边 也就是第一位 0 上是不是1，分成两组，然后有1的我们用eor去异或，自然就会得到其中出现奇数次的两个数中的一个，保存到res中，然后最后用res异或eor，就可以得到最后剩下的那个数
代码演示：
class Solution {
public int[] singleNumbers(int[] nums) {
int eor = 0;
for(int i=0;i < nums.length; i++){
eor ^= nums[i];
//最终eor会是这两个奇数次相异或的结果
//eor = a^b
}
int rightOne = eor & (~eor+1); // eor & (-eor)
int otherOne = 0; //两个数中的其他一个
for(int i = 0;i < nums.length; i++){
//我们最右边那个数 是 0000001000....
//如果数组中的这个数 & 最右边这个数字 不等于 0
//就代表这个位置一定是1
if((nums[i] & rightOne) != 0 ){
//也就是说我的otherOne 可能是 1^2^2^4^4....(假设)
//根据偶数相消，只会留下一个数字，就是结果之一
otherOne ^= nums[i];
}
}
//此时eor = a ^ b ，我们此刻求出a/b了
//res 就是剩下一个
int res = eor ^ otherOne;
int[] ans = {res,otherOne};
return ans;
}
}
数组中出现K次的数
一个数组中有一种数出现了K次，其他数出现了M次，M>1，K<M，求出现K次的数
剑指 Offer 56 - II. 数组中数字出现的次数 II
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。此题目中 k为1，M为3
解题思路：
我们通过一个32位的int数组来进行表示，举个例子，比如我的nums是{5,5,5,4,3,3,3}，那么我们都知道5的二进制是0101，3的二进制0011，4的二进制是0100，那么也就是说，在数组最后一位中，我们的数字类加就是6，也就是int[] nums = {00000000....000436}，也就是说6/3能整除，说明出现k次的数字最后一位不是1，3/3整除，k倒数第二位不是1，4/3有余数，那么k就在这里有1.
代码演示：
class Solution {
public int singleNumber(int[] arr) {
int[] t = new int[32];
for(int num : arr){
for(int i =0; i <= 31; i++){
//nums >> 0就是本身 &1 其实就是与00000001
//当 不等于0 哪一位就是1
// if(((num >> i) & 1) !=0 ){
// //如果不等于0，也就说那个位是1，所以我t[]这个位置类加1
// t[i]++;
// }
t[i] += (num >> i) & 1;
}
}
int ans = 0;
for(int i = 0; i < 32; i++){
//这个3 在不同题目中 可以换成M
if(t[i] % 3 != 0){
// 1<<移动位置到i项
// 然后或到ans里，就是在ans的位置上+1
/*
比如ans = 00000000;
此刻我的t[0] != 3 也就是说我的0位是1
1 << 0 是000000001
或进取 ans = 00000001
1 << 1 是000000010
或进取 ans = 00000011
*/
ans |= (1 << i);
}
}
return ans;
}
}
Hash表实现：
class Solution {
public int singleNumber(int[] arr) {
HashMap<Integer,Integer> map = new HashMap();
//遍历一下arr
for(int num : arr){
//如果map中包含这个num
if(map.containsKey(num)){
//那么map中的num的key 就+1
map.put(num,map.get(num)+1);
}else{
//否则就是map中没有这个num，就添加进去，然后num的key为1
map.put(num,1);
}
}
//把map的key都取出来遍历
for(int num:map.keySet()){
//如果key = 1 （也可以是k，m，n）
if(map.get(num) == 1){
return num;
}
}
return -1;
}
}