C 语言异或运算符的编程实用方法及应用场景总结

暂归纳了10种在编程中经常遇见的异或运算使用的方法。在单片机编程中对GPIO输出控制LED的闪烁原理也是如此,定义了一个宏,直接通过GPIOA口对ODR寄存器进行操作,异或PIN2的位。总之,异或运算是一种重要的二进制运算,在实际代码编程中有着广泛的应用。

C 语言异或运算符的编程实用方法及应用场景总结

1 简介

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

但是它的实际应用场景到底是怎么样的呢?或者说在一些编程技巧上应该怎么用呢?本文针对XOR运算符总结了一些实用的编程方法和思路,供大家参考。如果还有其他好用的函数,也可以一起分享。

2.基本原理和规律

首先我们需要明确异或运算的几个基本规则和规律,这为异或运算的巧妙运用提供了基础。

3. 使用归纳法

下面介绍编程中经常遇到的10种XOR运算的使用方法。

(1)快速比较两个值

例如,比较两个值时,我们通常使用 a==b。如果两个数相等,则 a ^ b 的结果为零。

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

(2)数据交换

XOR 运算的性质可用于交换两个数字,而无需使用额外的变量。

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里面来,直到进位等于0        a = 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中减掉,直到退位等于0        a = sum;        b = abdication;    }    return a;}

(4)数据备份

利用XOR还可以轻松实现多个数据的互相备份,假如有数据a,b,c,那么d=a^b^c,再备份数据d。

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

由此可见,备份一份数据d后,如果有其他数据丢失,可以通过将备份数据与其他数据进行异或运算来恢复,磁盘阵列技术raid5的数据备份原理就是利用了这个特性。

(5)数据加密与解密

当需要对数据进行简单的加密解密时,例如,可以使用XOR操作对明文数据进行加密解密。例如,明文数据为message,密钥为key,加密数据为secret。确保通信的发送方和接收方存储相同的密钥。密钥可以使用rand()生成一串随机数。例如:

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

美国数学家香农证明,只要满足下面两个条件,XOR加密就无法被破解。

原因很简单,如果密钥每次都是随机的,那么生成的秘密就具有所有可能的值,并且分布均匀。从秘密中看不出消息的任何特征。换句话说,它具有最大的“信息熵”,因此完全不可能被破解。这被称为XOR的“完美保密性”。为了使XOR加密更可靠,可以添加一些其他操作,例如对数据进行循环移位或反转。

(6)数据奇偶校验判断

由于异或运算要先转换成二进制数,所以偶数二进制数的最后一位一定是0,奇数二进制数的最后一位一定是1。

所以将待判断数与1异或的结果-待判断数==1,也就是说该数是偶数,否则就是奇数!

int a = 12345//a=123456if ((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;}

一个数组中有两个数出现的次数为奇数,其他数出现的次数均为偶数,如何找到这两个数呢?

步骤1:对所有数字进行异或得到re=a^b;

第二步:取出re最右边的“1”(取反、+1、以及其本身);

第三步:将所有数字与位“1”进行异或,结果为a或b;

步骤4:再次将两个结果进行“与”运算,得到另一个数字。

int* ReOddNum2(int arr[], int len){  int re = arr[0];  int rr[2] = { 0,0 };  //第一步:将所有数异或,得到a^b  for (int i = 1; i < len; i++)  {    re = arr[i] ^ re;  }  //第二步:提取re最右侧的“1”(取反,+1,自身相与)  int rightone = re&(~re + 1);  //第三步:将所有该位为“1”的数相异或,得到的数便为a或者b  int 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进行异或运算后都会得到原值的相反值,所以当我们需要对整数的某几位进行翻转时,可以利用按位异或运算来实现掩码运算,对相应的数据位进行翻转。

//定义一个整数nint a = 0x0f//二进制表示为00001111//如果需要翻转a的第4和第5位,则定义掩码maskint 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:归根结底,在布尔代数中,只需要AND、OR、NOT运算就能实现其他所有运算,所以XOR运算其实可以通过AND、OR、NOT来实现,最直观的表示如下:

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

结尾

单片机

树莓叶功效与作用大揭秘!美容养颜、润肠通便,你还不知道吗?

2024-5-29 9:04:31

单片机

51 单片机:遵循 51 指令集的超微型电脑,你了解多少?

2024-5-29 10:04:00

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索