大厂面试高频题之数据结构与算法|认识异或运算的本质与基本规律，0^x=x,x异或x=0，有交换律，结合律，与顺序无关 java|面试|数据结构|异或运算

认识异或运算的本质与基本规律，0^x=x,x异或x=0，有交换律，结合律，与顺序无关 提示：异或运算系列文章
非常重要的算法技巧：异或运算！！
为了破解以下这些重要的题目：
（2）数组arr中，有一个数k出现了奇数次，其他数出现偶数次，请找到并打印这个数k
（3）如何把一个数字x最右侧那个1拿出来，变成00…10…的格式
（4）如何统计一个数字x中1的个数
文章目录

认识异或运算的本质与基本规律，0^x=x,x异或x=0，有交换律，结合律，与顺序无关
- @[TOC](文章目录)
异或运算本质是啥？
扩展任意k>=2进制的异或：k进制不带进位的加法
k进制异或运算的基本规律
总结

异或运算本质是啥？不带进位的加法！
先来看二进制异或：就是k=2进制的不带进位加法。
我们有一个异或的口诀：同为0，不同为1：
比如11^3=8
即1011^0011=1000
两位碰，同为0，不同为1

大厂面试高频题之数据结构与算法|认识异或运算的本质与基本规律，0^x=x,x异或x=0，有交换律，结合律，与顺序无关

文章图片

那么异或的本质是啥呢？
不带进位的加法！！！
还是上面这例子：

文章图片

扩展任意k>=2进制的异或：k进制不带进位的加法【未来，我们会——在高频面试题那，碰到很有代表性的大厂高频题：用k进制异或解决！】
（1）比如说吧，k=4,4进制异或是啥意思呢？一样啊
就是4进制数，它不需要带进位，做加法即可，没啥区别
比如，12332 ^ 21332=33221
【在这你要迅速转换脑子，4进制，0123，代表4进制的取值】
4进制不进位加法就是：4进制异或
2+2=4（10进制的）=10（4进制的）,1是进位，不要
3+3=6（10进制的）=12（4进制的），1是进位，不要
2+1=3，就是4进制的3
1+2=3，就是4进制的3

文章图片

（2）再来一个简单点的，k=3，那取值为012，故整个数x中，最多取2,
比如：2+1=10（10不是十进制的10哦，而是3进制的3，就像二进制10一样，是2进制的2）=3
好请你求3进制异或：
1210^1222=2132
其中：2+0=0
1+2=10，1进位不要
2+2=11，前面那个1进位不要
1+1=2
最后就得到不带进位的加法：3进制异或

文章图片

现在你明白了2进制的异或了吧，甭管k=23456……
k进制异或就是k进制的不带进位的加法，随意！！！
k进制异或运算的基本规律不管是k=23456……
异或运算都有一个基本规律：记住了
（1）x^0=x; x异或0就是x本身
（2）x^x=0; x异或x本身是0
（3）异或运算有交换律，结合律，与顺序无关！
怎么理解？
（1）x^0=x; x异或0就是x本身
知道了异或的本质是k进制不带进位加法之后，那就好说了
比如：x=7
7^0=7

文章图片

（2）x^x=0; x异或x本身是0

文章图片

【大厂面试高频题之数据结构与算法|认识异或运算的本质与基本规律，0^x=x,x异或x=0，有交换律，结合律，与顺序无关】（3）异或运算有交换律，结合律，与顺序无关！
7异或0异或7

文章图片

7异或7异或0

文章图片

谁跟谁先结合，不影响整体异或结果，只与各个位的数字有关
所以呢？
偶数个x异或=0
奇数个x异或=x
为啥呢？
用上面3条规律：

文章图片

文章图片

所以这个关于异或的基础知识，一定要掌握，今后在算法题中有很多用处的！
代码自己验证一下就知道：

//学一些基础的知识 public static void baseKnowledge(){ //两个数字的异或a^b是每一个加法都不进位的相加 //N^0==N,N^N=0; 因为不进位加，任何数字与N异或完都是自己，自己异或自己=0， int N = 7; System.out.println(N ^ 0); System.out.println(N ^ N); System.out.println(N^N^N); //奇数次自己异或自己，还是自己！！ System.out.println(N^N^N^N); //偶数次异或自己，为0，因为上面那两条铁律！！ }

总结 提示：重要经验：
1）异或运算的本质就是k进制不带进位加法！
2）异或有3条规律，x异或0=x，x异或x=0，异或不考虑顺序