设计素材网站合集seo外包网站
数据结构----异或
一.何处用到了异或
1. ==运算符
== //判断是否相同 用到了异或，看异或结果如果是0就是相同，不是0就是不同//注意：== 不能给小数用，小数没有相等的概念，所以小数判断是否相同都是进行相减判断
2.找一堆数中只出现一次（奇数次）的数字
前提：最多有两个只出现一次（奇数次）的数字
3.内存清零
自己异或自己
4.交换
不用第三个变量进行交换的方法
//加减法
int a;
int b;a=a+b;
b=a-b;
a=a-b;
//异或
int a;
int b;if(a^b){//先判断是否相同，相等的话就不换了
a=a^b;
b=a^b;
a=a^b;
}二.不用“+ - * /”实现加法
方法：
1.两个数先异或 （得到的是不进位的数）
2.两个数再相与 （得到的是进位的数右移一位的数，所以下一步要进行左移）
3.相与得到的数据再进行一次左移 （得到的是进位的数）
4.将第一步和第三步获得的数从第一步继续进行操作，直到第3步获得的数为0时结束（进位为0时）
代码如下
int Add(int a, int b) {int And=0;int Xor=0;while (1) {And = a & b;Xor = a ^ b;//不进位if (!And) {return Xor;}//进位And = And << 1;a = And;b = Xor;}
}
三.格雷码（异或的应用）
//二进制
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 1
1 0 0 0
//二进制格雷码
0 0 0 0
0 0 0 1
0 0 1 1
0 0 1 0
0 1 1 0
0 1 1 1
0 1 0 1
0 1 0 0
1 1 0 0
如何从二进制转换到二进制格雷码（异或）
二进制高位(第一位)保留 获得二进制格雷码高位(第一位）
二进制第二位与二进制第一位异或 获得二进制格雷码的第二位
二进制第三位与二进制第二位异或 获得二进制格雷码的第三位
以此类推可得
如 0 0 1 0 变为 0 0 1 1
如何从二进制格雷码转换到二进制（异或）
二进制格雷码高位(第一位)保留 获得二进制高位(第一位）
二进制格雷码第二位与二进制第一位异或 获得二进制的第二位
二进制格雷码第三位与二进制第二位异或 获得二进制的第三位
以此类推可得
如 0 0 1 0 变为 0 0 1 1
看一道与格雷码知识有关的题
力扣第1611题
题目: 给你一个整数 n，你需要重复执行多次下述操作将其转换为 0 ：
- 翻转
n的二进制表示中最右侧位（第0位）。 - 如果第
(i-1)位为1且从第(i-2)位到第0位都为0，则翻转n的二进制表示中的第i位。
返回将 n 转换为 0 的最小操作次数
这里的两种操作方法是格雷码的两种翻转方式
0 二进制 0 0 0 0 对应二进制格雷码 0 0 0 01 二进制 0 0 0 1 对应二进制格雷码 0 0 0 12 二进制 0 0 1 0 对应二进制格雷码 0 0 1 1 //0到1
二进制格雷码发生的就是第一次翻转方法
//1到2
二进制格雷码发生的就是第二次翻转方法 //二进制格雷码这种翻转方式是交替进行的（如上面0到1，1到2）
解题方法：1.将这个数看成是格雷码
2.将这个格雷码转换成二进制
3.根据二进制的数值写出最少操作次数