经典算法之异或运算（无进位相加）

目录

• 异或运算的定义
• 异或运算的性质
• 异或运算的应用
• • 交换两数
  • 翻转指定位
  • 寻���单身狗

    异或运算的定义

    众所周知，计算机中的所有数据都是以二进制（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
    下面我们用程序来验证一下：

    #includeint 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 。

    异或运算的应用

    交换两数

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

    #includeint 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位进行翻转，并打印反转后的十进制数
    代码如下：

    #includeint 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        eor=eor^nums[i];    }    return eor;}