河北省网站快速备案,网站建设 销售提成,vps 同时做ssh和做网站,北京三屏网站制作数据结构----异或
一.何处用到了异或
1. 运算符 //判断是否相同 用到了异或#xff0c;看异或结果如果是0就是相同#xff0c;不是0就是不同//注意#xff1a; 不能给小数用#xff0c;小数没有相等的概念#xff0c;所以小数判断是否相同都是进行相减判断2.找一堆数中…数据结构----异或
一.何处用到了异或
1. 运算符 //判断是否相同 用到了异或看异或结果如果是0就是相同不是0就是不同//注意 不能给小数用小数没有相等的概念所以小数判断是否相同都是进行相减判断2.找一堆数中只出现一次奇数次的数字
前提最多有两个只出现一次奇数次的数字
3.内存清零
自己异或自己
4.交换
不用第三个变量进行交换的方法
//加减法
int a;
int b;aab;
ba-b;
aa-b;//异或
int a;
int b;if(a^b){//先判断是否相同相等的话就不换了
aa^b;
ba^b;
aa^b;
}
二.不用“ - * /”实现加法
方法
1.两个数先异或 得到的是不进位的数
2.两个数再相与 得到的是进位的数右移一位的数所以下一步要进行左移
3.相与得到的数据再进行一次左移 得到的是进位的数
4.将第一步和第三步获得的数从第一步继续进行操作直到第3步获得的数为0时结束进位为0时
代码如下
int Add(int a, int b) {int And0;int Xor0;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到11到2解题方法1.将这个数看成是格雷码
2.将这个格雷码转换成二进制
3.根据二进制的数值写出最少操作次数
