认识异或运算的本质与基本规律，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 那么异或的本质是啥呢？ 不带进位的加法！！！ 还是上面这例子： 扩展任意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 （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，异或不考虑顺序