虚拟空间做网站2345电脑版网址导航

目录

1、前言

2、基本准则定律

3、妙用归纳

4、总结

---

1、前言

        C语言中异或运算符^作为一个基本的逻辑运算符，相信大家都知道其概念：通过对两个相同长度的二进制数进行逐位比较，若对应位的值不同，结果为 1, 否则结果为 0。

        但是它在实际使用中到底会有哪些应用场景或者说是有在一些编程技巧中该如何使用，本文总结归纳了一些异或运算符的编程时实用方法思路以供参考，如有其它好用的功能，也可提出一起分享。

---

2、基本准则定律

        首先需要明确的是异或运算的几个基本准则定律，这些准则定律为异或运算的巧妙应用提供了基础。

• 交换律：对于任意变量 a 和 b，a ^ b 等于 b ^ a。

• 结合律：对于任意变量 a、b 和 c，(a ^ b) ^ c 等于 a ^ (b ^ c)。

• 自反性：任何数与自身进行异或操作结果为0，即 a ^ a = 0。

• 零元素性质：任何数与0进行异或操作结果为自身，即 a ^ 0 = a。

• 分配律：a ^ (b & c) = (a ^ b) & (a ^ c)，其中 & 表示按位与操作。

• 奇偶性：一个数字和1做异或运算，可以判断它的奇偶性。如果结果为0，表示这个数字是偶数，如果结果为1，表示这个数字是奇数。

---

3、妙用归纳

        暂归纳了10种在编程中经常遇见的异或运算使用的方法。

（1）两个值的快速比较

        例如比较两个值是否相等时，一般我们使用这个 a==b，如果两个数相等 ，a ^ b 的结果为零。

if(a^b == 0) {//a和b若相同则为true 
}

（2）数据交换

        利用异或运算的性质可以进行两个数的交换，不会利用额外的变量。

void swap()
{ a=a^b;b=b^a;a=b^a;
}

        注意利用异或运算进行数据交换有个前提：要交换的两个数必须在在不同的内存，不然会出现问题。如果 a 和 b 是同一个地址呢？比如，我们调用的是 swap(a[i], a[j])，当 i == j时，利用异或运算进行数据交换是错误的。

        在这种情况下，我们第一步做的 a ^= b，实际上就是 a[i] ^= a[i]。这将直接让a[i]中的元素等于0，而丢失原本存在a[i]中的元素。后续这个元素就再也找不回来了。针对这个问题解决方案是在做这个交换之前，判断一下 a 和 b的地址是否相同。也可以把逻辑改变为，判断一下a和b是否相同。如果相同，则什么都不做。

（3）加减法

        如二进制加法01 + 01 = 10，而异或运算是01 ^ 01 = 00，它其实做了加法，但高位不进位，所以异或又称不进位加法。

        如二进制减法10 - 01 = 01，而异或运算是10 ^ 01 = 11，也可以看做个位0向高位借了一个1当2来用，但高位不减1，所以异或也可以称为不退位减法。

        利用异或的这个特性，只要再解决一下进位和退位问题，就可以实现加减法了。这也是为什么CPU里面都是做位运算的逻辑门电路，却能实现数值计算。

int plus(int a, int b) {int sum, addition;while (b != 0) {// 加法(未考虑进位)sum = a ^ b;// 进位值，二进制中1 + 1的场景才会进位，//a & b只有两个都为1，结果才是1，左移一位，就是进位值了addition = (a & b) << 1;// 赋值，下次循环将进位加到a里面来，直到进位等于0a = sum;b = addition;}return a;
}int subtraction(int a, int b){int sum, abdication;while (b != 0){// 减法(未考虑退位)sum = a ^ b;// 退位值，二进制中0 - 1的场景才会退位，//~a & b只有a=0,b=1，结果才是1，左移一位，就是退位值了abdication = (~a & b) << 1;// 赋值，下次循环将退位再从a中减掉，直到退位等于0a = sum;b = abdication;}return a;
}

（4）数据备份

        使用异或也可以很容易实现多个数据的互相备份，假如有数据a、b、c，则d = a ^ b ^ c，然后把数据d备份下来。

当a丢失时，可使用d ^ b ^ c来恢复
当b丢失时，可使用d ^ a ^ c来恢复
当c丢失时，可使用d ^ a ^ b来恢复

        由此可见备份了一份数据d后，丢失了其他任何一个数据，都可以通过备份数据与其它数据异或恢复回来，磁盘阵列技术raid5的数据备份原理，用的就是这个特性。

（5）数据加解密

        在例如通信时需要对数据使用简单的加解密方法时，使用异或操作可以进行明文数据的加解密，。比如明文数据是message，密钥是key，加密后的数据是secret，确保通信发送方和通信接收方都存储了相同的key，key可以使用rand()生产一串随机数，则举例说明：

// 加密
secret = message ^ key
0x2C0E = 0x89AB ^ 0xA5A5
// 解密
message = secret ^ key
0x89AB = 0x2C0E ^ 0xA5A5

        美国数学家香农证明了只要满足以下两个条件，异或加密是无法破解的。

• key的长度大于等于message。

• key必须是一次性的，且每次都要随机产生。

        理由很简单，如果每次的 key 都是随机的，那么产生的secret具有所有可能的值，而且是均匀分布，无法从secret看出 message 的任何特征。也就是说，它具有最大的"信息熵"，因此完全不可能破解。这被称为异或的"完美保密性"。为了让异或加密更可靠，可以添加一些其他操作，例如对数据进行循环位移或取反的操作。

（6）数据奇偶数判断

        由于异或运算要先转化为二进制数，而偶数的二进制数的最后一位必定是0，奇数的二进制数的最后一位必定是1。

        因此，要判断的数与1异或得到的结果 - 要判断的数==1，说明该数是偶数，反之是奇数！

int a = 12345; //a=123456
if ((a ^ 1) - a == 1) {"是偶数！";
} else {"是奇数！";
}

（7）出现奇偶次的找数问题

        一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到这一个数？

        分析：利用异或性质a ^ a=0，则出现偶数的数字相异或为0，而出现奇数次的异或结果为本身，那么，将所有的数异或后，就是要找的这个出现奇数次的数。

int ReOddNum1(int arr[], int len)
{int re = arr[0];for (int i=1;i<len;i++){re = arr[i] ^ re;}return re;
}

        一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到这两个数？

        step1：将所有数异或，得到re=a^b；

        step2：提取re最右侧的“1”（取反，+1，自身相与）；

        step3：将所有该位为“1”的数相异或，得到的数便为a或者b；

        step4：再次相与两个结果，得到另一个数。

int* ReOddNum2(int arr[], int len)
{int re = arr[0];int rr[2] = { 0,0 };//第一步：将所有数异或，得到a^bfor (int i = 1; i < len; i++){re = arr[i] ^ re;}//第二步：提取re最右侧的“1”（取反，+1，自身相与）int rightone = re&(~re + 1);//第三步：将所有该位为“1”的数相异或，得到的数便为a或者bint re1 = 0;for (int i = 0; i < len; i++){if ((arr[i]&rightone)!=0){re1 = arr[i] ^ re1;}    }rr[0] = re1;//第四步：再次相与两个结果，得到另一个数rr[1] = re1^re;return rr;  
}

（8）奇偶校验

        首先先看一个例子理解下：判断一个二进制数中1的数量是奇数还是偶数。

        求10110101中出现1的数量是奇数还是偶数；可将10110101逐位异或操作，结果为1就是奇数个1，结果为0就是偶数个1。

        奇校验：原始码+1位校验位，总共有奇数个1；

        偶校验：原始码+1位校验位，总共有偶数个1。

        比如为原始码添加奇偶校验位：

        原始码：1101010

        判断1的个数是否为偶数：1^1^0^1^0^1^0=0，因为逐位异或的结果为0，所以1的个数为偶数，奇校验则在原数据末尾添1，变成11010101；偶校验则在原数据末尾添0，变成11010100。

（9）对某些特定的位翻转

        由于不管是0或者1与1做异或操作后将得到原值的相反值，因此当我们需要翻转一个整数的某些位时，我们可以使用位异或运算来实现掩码操作，将对应的数据位进行翻转。

//定义一个整数n
int a = 0x0f; //二进制表示为00001111
//如果需要翻转a的第4和第5位，则定义掩码mask
int mask = 0x18; //二进制表示为00011000
//使用位异或运算翻转n的第3位和第4位
n = n ^ mask; //结果为二进制表示为00010111

        在单片机编程中对GPIO输出控制LED的闪烁原理也是如此，定义了一个宏，直接通过GPIOA口对ODR寄存器进行操作，异或PIN2的位。实现引脚PA2输出高低电平的翻转控制LED闪烁。

// PA2引脚输出电平翻转
#define LED_TOGGLE() GPIOA->ODR ^= GPIO_PIN_2

（10）数据符号判断

        例如判断两个int32类型的数据的符号是否相同，其中31是符号位的偏移量：

if (((a ^ b) >> 31) & 1) {"符号不相同！";
} else {"符号相同！";
}

---

4、总结

        总之，异或运算是一种重要的二进制运算，在实际代码编程中有着广泛的应用。需要深刻的去理解异或运算符的几条基本准则定律，就能够快速地完成数字的交换、计算、去重等操作，为我们在功能开发中提供便利。

        小tips：归根到底在布尔代数中，其实只需要与、或、非运算就可以实现所有其它运算，所以异或运算实际可以通过与、或、非实现，最直观的表示方式如下：

a ^ b = (~a & b) | (a & ~b)  

---

↓↓↓更多技术内容和书籍资料获取，入群技术交流敬请关注“明解嵌入式”↓↓↓