本文已收录于专栏 🌸《Java入门一百例》🌸

序、专栏前言

   本专栏开启，目的在于帮助大家更好的掌握学习Java，特别是一些Java学习者难以在网上找到系统地算法学习资料帮助自身入门算法，同时对于专栏内的内容有任何疑问都可在文章末尾添加我的微信给你进行一对一的讲解。
   但最最主要的还是需要独立思考，对于本专栏的所有内容，能够进行完全掌握，自己完完全全将代码写过一遍，对于算法入门肯定是没有问题的。
   算法的学习肯定不能缺少总结，这里我推荐大家可以到高校算法社区将学过的知识进行打卡，以此来进行巩固以及复习。
  学好算法的唯一途径那一定是题海战略，大量练习的堆积才能练就一身本领。专栏的任何题目我将会从【题目描述】【解题思路】【模板代码】【代码解析】等四板块进行讲解。

一、异或运算

• $(1)$异或运算符是^，它和前两篇文章讲的&与|一样，也是一个二元运算符，表示为x^y。
• $(2)$^同样是对二进制进行运算，二进制只有0和1，所以出现的组合情况也只有$2^2=4$种，将其写成表格形式很容易探究出其规律。

• 仔细对比表格中的规律
• $(1)$异或运算^，顾名思义，只有当操作数不相同时才为1，否则为0。也就是同值取0，异值取1。

public class Main {
    public static void main(String[] args) {
        int a=0b10101;//21
        int b=0b01010;//10
        System.out.println(a^b);//31
    }
}
1
2
3
4
5
6
7

• $(2)$在Java中，以0b开头，表示这是一个二进制串，a的十进制值应该为$(10101{)}_2=21$,b的十进制值应该是$(01010{)}_2=10$，这里b的前导0可以省去，写在这是为了和a产生对比。
• $(3)$根据^运算的规则，答案为$(11111{)}_2$，转换为十进制最终结果为31
• $(4)$根据异或的规则，我们可以得到两条重要的式子，首先是a^a=0，任意一个数异或自己的结果都为0，因为两个数相等则二进制表示完全一样。a^0=a，任意数异或0的结果仍然为自己。
• $(4)$^运算也是十分重要的一种位运算，我们来逐步分析其具有哪些性质吧。

1.不进位加法

  很明显，我们只要上过小学的都知道，在数学加法中，都会满足下列式子，1+1=10，0+0=0，1+0=1，当然这里是使用二进制来运算。而我们的^运算则有，1^1=0,0^0=0,1^0=1，我们发现除了产生进位时，^运算它不进位，其余运算都和加分的结果一样，所以异或运算也被称之为不进位加法。

2.异或的三种特性

• $(1)$ 交换律： 这非常容易理解，即$X\stackrel{ˆ}{}Y=Y\stackrel{ˆ}{}X$，当然任意多位数进行异或也可以随意调换位置，不影响答案。
• $(2)$结合律 即满足$(X\stackrel{ˆ}{}Y)\stackrel{ˆ}{}Z=X\stackrel{ˆ}{}(Y\stackrel{ˆ}{}Z)$
• $(3)$ 自反性 即满足$X\stackrel{ˆ}{}Y\stackrel{ˆ}{}Y=X$ ，这一点可结合前面异或的特性以及结合律得到$X\stackrel{ˆ}{}Y\stackrel{ˆ}{}Y=X\stackrel{ˆ}{}(Y\stackrel{ˆ}{}Y)=X\stackrel{ˆ}{}0=X$

二、异或的运用

1、交换两数

   给定两个正整数 $a$ 和 $b$ ，请你在不创建第三个变量的情况下，交换两数的值。

1、解题思路

• $(1)$这是^运算的经典用法，也是面试偶尔会遇到的题

2、模板代码

public class Main {
    public static void main(String[] args) {
        int a=10;
        int b=5;
        a^=b;
        b^=a;
        a^=b;
        System.out.println(a+" "+b);
    }
}
1
2
3
4
5
6
7
8
9
10

3、代码解析

$(1)$当a^b=c时，同时满足a^c=b，b^c=a。执行第一步后，a==c，第二步当b^a也就等价于b=b^c=a，最后a=a^b=c^a=b，完成我们的目的。

2.排除偶次重复

   给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

1、解题思路

• $(1)$也是^的经典用法，它可以抵消去除出现偶数次的数字，最后只留下出现奇数次的数字，将所有数字异或即可获得答案。

2、模板代码

class Solution {
    public int singleNumber(int[] nums) {
        int b=0;
        int n=nums.length;
        for(int i=0;i<n;++i){
            b^=nums[i];
        }
        return b;
    }
}
1
2
3
4
5
6
7
8
9
10

3、代码解析

• $(1)$相同的数^结果为0，任何数与0异或结果为自己，让数组所有数进行异或最后剩下的则是出现一次的数字。

三、推荐专栏

🌌《零基础学算法100天》🌌

四、课后习题

👇 学习有疑问？👇