经典算法之异或运算(无进位相加)

简介: 经典算法之异或运算(无进位相加)

异或运算的定义

众所周知,计算机中的所有数据都是以二进制(0或者1)的形式存储。而异或运算符(^)就是将参加运算的两个数据,按二进制位进行"异或"运算。那么异或运算是如何进行的呢?
异或运算:将参与运算的两个数转化为2进制后相同位置相同则为0相异则为1,但是需要注意,参加运算的两个操作数必须为整数,不能为浮点数。
下面我们用一个实际的小栗子来解释,异或运算在计算机中具体是如何实现的的。

例如:计算3^5的结果

我们先将3和5都转为二进制的形式:
3:0000 0000 0000 0000 0000 0000 0000 0011
5:0000 0000 0000 0000 0000 0000 0000 0101
按照异或运算的运算规律:相同位置相同则为0相异则为1

3^5: 0000 0000 0000 0000 0000 0000 0000 0110

而这个结果转化为十进制就是:6
下面我们用程序来验证一下:

#include<stdio.h>
int main()
{
    int a = 3;
    int b = 5;
    printf("a^b的结果为:%d\n", a ^ b);
    return 0;
}

运行结果:

在这里插入图片描述

异或运算的性质

异或运算符是一个二元的位运算符,也就是说有左右两个操作数,表示为a^b。
因为二进制的每一位只有0和1两个数,所以我们不妨列个表格。

a b a^b
0 0 0
0 1 1
1 0 1
1 1 0

不难发现,两个操作数,相同为0 不同为1。我们也可也这样理解:异或运算就是无进位相加。什么意思呢?用我们熟悉十进制的角度来看,比如我需要计算5+5,如果正常情况下,我们的计算结果应该是10,10拆开来看,10的个位数是0,十位数是1,可以理解为是两个个位数为5相加后进一的结果。如果不进位那就应该是00。当然十进制中并没有这种运算。
由于二进制每一位的数只有0或1,如果不进位,那么就是两个数相同就是0,相异就是1。
由此,我们得到了如下的性质:

1.两个相同的十进制数异或的结果一定为零。
2.任何一个数和 0 的异或结果一定是它本身。
3.异或运算满足结合律:a ^ b ^ c = ( a ^ b )^ c = a ^ ( b ^ c ) 。
4.异或运算满足交换律:a ^ b= b ^ a 。

异或运算的应用

交换两数

题目:不用任何变量交换两个数
代码如下:

#include<stdio.h>
int main()
{
    int a = 5;
    int b = 6;
    printf("交换前:");
    printf("%d  %d\n", a,b);
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
    printf("交换后:");
    printf("%d  %d\n", a,b);
    return 0;
}

解释:
第一次异或运算:a = a^b
第二次异或运算:注意此时a已经变成了a ^ b,所以此时b=a ^ b ^ b
根据异或运算的性质:两个相同的数异或一定会被消掉,这里两个b异或就被消掉了,此时b=a
第三次异或运算:此时b=a而a=a ^ b,所以此时a^b应该为:a ^ b^a,同样根据性质,消掉了两个a,所以此时a = b 完成了交换。

翻转指定位

例如:将数 X=1010 1001 的低4位进行翻转,并打印反转后的十进制数
代码如下:

#include<stdio.h>
int main()
{
    int a = 0b10101001;
    int b = 0b00001111;
    int c = a ^ b;
    printf("a:%d\n", a);
    printf("b:%d\n", b);
    printf("a^b:%d\n", c);
    return 0;
}

打印结果:

在这里插入图片描述

166的二进制是:1010 0110
169的二进制是:1010 1001
很容易就可以看出,第四位全部被翻转了。
解释:
根据异或运算的性质可以得出,任何一个数与0异或运算都是它本身,所以对于不想翻转的位置全部写0,而对于想翻转的位置,写1就行了。

寻找单身狗

在这里插入图片描述

int singleNumber(int* nums, int numsSize)
{
    int eor = 0;
    for(int i = 0;i<numsSize;i++)
    {
        eor=eor^nums[i];
    }
    return eor;
}

解释:
异或运算就和 消消乐 一样。
两个相同的数异或一定为0,而其它数异或0的结果都是本身。
当我们的有很多数在一起异或的时候,出现偶数次的数一定会被消掉 ,最后留下的一定是出现奇数次的数。

相关文章
|
算法 Java C++
试题 算法训练 集合运算
试题 算法训练 集合运算
70 1
|
算法
算法基础:高精度运算
算法基础:高精度运算
145 0
|
算法 搜索推荐 C++
【C++STL基础入门】vector运算和遍历、排序、乱序算法
【C++STL基础入门】vector运算和遍历、排序、乱序算法
628 0
|
存储 算法
【算法基础】高精度运算
【算法基础】高精度运算
153 0
|
算法
聊聊一个面试中经常出现的算法题:组合运算及其实际应用例子
聊聊一个面试中经常出现的算法题:组合运算及其实际应用例子
121 1
|
算法 Java
Java数据结构与算法:位运算之与、或、异或运算
Java数据结构与算法:位运算之与、或、异或运算
|
算法
数据结构和算法学习记录——层序遍历(层次遍历)、二叉树遍历的应用(输出二叉树中的叶节点、求二叉树的高度、二元运算表达式树及其遍历、由两种遍历序列确定二叉树)
数据结构和算法学习记录——层序遍历(层次遍历)、二叉树遍历的应用(输出二叉树中的叶节点、求二叉树的高度、二元运算表达式树及其遍历、由两种遍历序列确定二叉树)
216 0
|
算法 C++
c++算法学习笔记 (4)高精度运算
c++算法学习笔记 (4)高精度运算
|
算法 Python
算法创作|用python解决简单的数学运算
算法创作|用python解决简单的数学运算
189 0
|
算法 C++
【C++算法图解专栏】一篇文章带你掌握高精度加减乘除运算
【C++算法图解专栏】一篇文章带你掌握高精度加减乘除运算
326 0

热门文章

最新文章