精华内容
下载资源
问答
  • 异或运算

    万次阅读 多人点赞 2017-11-17 18:45:11
    异或运算

    异或

    https://www.lijinma.com/blog/2014/05/29/amazing-xor/

    什么是异或?

    Wikipedia的解释:

    在逻辑学中,逻辑算符异或(exclusive or)是对两个运算元的一种逻辑析取类型,符号为 XOR 或 EOR 或 ⊕(编程语言中常用^)。但与一般的逻辑或不同,异或算符的值为真仅当两个运算元中恰有一个的值为真,而另外一个的值为非真。转化为命题,就是:“两者的值不同。”或“有且仅有一个为真。”

    定义:

    1 ⊕ 1 = 0

    0 ⊕ 0 = 0

    1 ⊕ 0 = 1

    0 ⊕ 1 = 1

    真值表:

      Y B = 0 B = 1
      A = 0 0 1
      A = 1 1 0

    表达式:

    Y = A’ · B + A · B’

    解释:我使用·作为,我使用+作为,我使用'作为(本来应该使用头上一横,但是太难编辑了,就使用了');

    异或有什么特性?

    根据定义我们很容易获得异或两个特性:

    恒等律:X ⊕ 0 = X 归零律:X ⊕ X = 0

    然后我们使用真值表可以证明:

    (1)交换律

    1
    2
    3
    
    A ⊕ B = A' · B + A · B'
    
    B ⊕ A = B' · A + B · A'

    因为·与+或两个操作满足交换律,所以:

    A ⊕ B = B ⊕ A

    (2)结合律

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    
    (A ⊕ B) ⊕ C
    
    = (A' · B + A · B') ⊕ C
    
    = (A' · B + A · B')' · C + (A' · B + A · B') · C '
    
    = ((A' · B)' · (A · B')')· C + A' · B · C ' + A · B' · C '
    
    = ((A + B') · (A' + B))· C + A' · B · C ' + A · B' · C '
    
    = (A · B + A' · B') · C + A' · B · C ' + A · B' · C '
    
    = A · B · C + A' · B' · C + A' · B · C ' + A · B' · C '
    

    你可以使用同样推导方法得出(请允许我偷懒一下,数学公式敲起来不容易 +_+):

    1
    2
    3
    
    A ⊕ (B ⊕ C)
    
    = A · B · C + A' · B' · C + A' · B · C ' + A · B' · C '

    证明过程中使用了如下几个方法(·与 +或 '否):

    ·与 +或交换律:

    1
    2
    3
    
    A · B = B · A
    
    A + B = B + A

    ·与 +或结合律:

    1
    2
    3
    
    (A · B) · C = A · (B · C)
    
    (A + B) + C = A + (B + C) 

    ·与 +或分配律:

    1
    2
    3
    
    A · (B + C)= A · B + A · C
    
    A + B · C = (A + B) · (A + C)

    摩尔定理:

    1
    2
    3
    
    (A · B)' = A' + B'
    
    (A + B)' = A' · B'

    结论:

    交换律:A ⊕ B = B ⊕ A 结合律:A ⊕ (B ⊕ C) = (A ⊕ B) ⊕ C

    有了归零率结合律,我们就可以轻松证明:

    自反:A ⊕ B ⊕ B = A ⊕ 0 = A

    可能这些特性会很顺其自然的理解,但是如果你在解决问题的时候,你可能会忘记异或的这些特性,所以适当的应用可以让我们加深对异或的理解;

    1
    2
    3
    4
    
    A ⊕ 1 = A';
    A ⊕ 0 = A;
    A ⊕ A = 0;
    A ⊕ A' = 1;

    异或有什么神奇之处(应用)?

    说明:以下的的异或全部使用符号^

    可能你已经被乱七八糟的公式和演算搞的有点烦了,不就是很简单的异或运算吗?还解释的那么复杂,嘿嘿,不要着急,打好了基础,你就站在了巨人的肩膀,让我们开始异或的神奇之旅吧;

    (1)快速比较两个值

    先让我们来一个简单的问题;判断两个int数字a,b是否相等,你肯定会想到判断a - b == 0,但是如果判断a ^ b == 0效率将会更高,但是为什么效率高呢?就把这个给你当家庭作业吧,考虑下减法是如何实现的; 让我们看看ipv6中的比较;

    1
    2
    3
    4
    5
    6
    7
    
    static inline int ipv6_addr_equal(const struct in6_addr *a1, const struct in6_addr *a2)
        {
        return (((a1->s6_addr32[0] ^ a2->s6_addr32[0]) |
            (a1->s6_addr32[1] ^ a2->s6_addr32[1]) |
            (a1->s6_addr32[2] ^ a2->s6_addr32[2]) |
            (a1->s6_addr32[3] ^ a2->s6_addr32[3])) == 0);
        }
    

    (2)在汇编语言中经常用于将变量置零:xor a,a

    (3)我们可以使用异或来使某些特定的位翻转,因为不管是0或者是1与1做异或将得到原值的相反值;

    0 ^ 1 = 1

    1 ^ 1 = 0

    例如:翻转10100001的第6位, 答案:可以将该数与00100000进行按位异或运算;10100001 ^ 00100000 = 10000001

    我们给出一段常用的代码:

    1
    2
    3
    
    unsigned int a, b, mask = 1 << 6;
    a = 0xB1; // 10100001
    b = a ^ mask; /* flip the 6th bit */
    

    (4)我们使用异或来判断一个二进制数中1的数量是奇数还是偶数

    例如:求10100001中1的数量是奇数还是偶数; 答案:1 ^ 0 ^ 1 ^ 0 ^ 0 ^ 0 ^ 0 ^ 1 = 1,结果为1就是奇数个1,结果为0就是偶数个1; 应用:这条性质可用于奇偶校验(Parity Check),比如在串口通信过程中,每个字节的数据都计算一个校验位,数据和校验位一起发送出去,这样接收方可以根据校验位粗略地判断接收到的数据是否有误

    (5)校验和恢复

    校验和恢复主要利用的了异或的特性:IF a ^ b = c THEN a ^ c = b 应用:一个很好的应用实例是RAID5,使用3块磁盘(A、B、C)组成RAID5阵列,当用户写数据时,将数据分成两部分,分别写到磁盘A和磁盘B,A ^ B的结果写到磁盘C;当读取A的数据时,通过B ^ C可以对A的数据做校验,当A盘出错时,通过B ^ C也可以恢复A盘的数据。

    RAID5的实现比上述的描述复杂多了,但是原理就是使用 异或,有兴趣的同学看下RAID5

    (6)经典题目:不使用其他空间,交换两个值

    1
    2
    3
    
    a = a ^ b;
    b = a ^ b; //a ^ b ^ b = a ^ 0 = a;
    a = a ^ b;
    

    这个题目就不用解释了吧,太大众题目了,哈哈,但是非常好的使用的了异或的特性;

    (7)面试题:互换二进制数的奇偶位;

    题目:写一个宏定义,实现的功能是将一个int型的数的奇偶位互换,例如6的2进制为00000110,(从右向左)第一位与第二位互换,第三位与第四位互换,其余都是0不需要交换,得到00001001,输出应该为9;

    思路:我们可以把我们的问题分为三步(难道这也是分治法吗 -。-),第一步,根据原值的偶数位获取到目标值的奇数位,并把不需要的位清零;第二步,根据原值的奇数位获取到目标值的偶数位,并把不需要的位清零;第三步:把上述两个残缺的目标值合并成一个完整的目标值;

    代码为:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    
    //假设 int 占两个字节,16位;
    #include<iostream>
    #include<string>
    using namespace std;
    #define N(n) ((n<<1)&(0xAAAA))|((n>>1)&(0x5555))
    void main(){
        int k = N(6);
        cout << k << endl;
    }
    

    解释: 1.为简化说明,我们以4位二进制码为例,0xAAAA 我们用 1010 代替;0x5555 我们用 0101 代替; 2.(n<<1)&(1010) 把n先左移1位,再与1010做与运算,只保留移位之后的偶数位的值,奇数位全为0,实际上是只保留了n的奇数位的值,并把它们交换到了偶数位上。比如 n = 0110 , n<<1 = 1100, (n<<1) & 1010 = 1000 ; 3.(n>>1)&(0101) 把n右移一位,再与 0101 做与运算,只保留移位之后的奇数位的值,偶数位全为0,实际是只保留n 的偶数位的值,并把它们交换到对应的奇数位上。n = 0110; n>>1 = 0011; (n>>1) & 0101 = 0001; 4.最后做或运算(相加),得到1001。

    (7)最最常出现的面试题:一个整型数组里除了N个数字之外,其他的数字都出现了两次,找出这N个数字;

    比如,从{1, 2, 3, 4, 5, 3, 2, 4, 5}中找出单个的数字: 1

    让我们从最简单的,找一个数字开始;

    题目:(LeetCode 中通过率最高的一道题) Single Number: Given an array of integers, every element appears twice except for one. Find that single one. Note:Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? 思路: 拿到这个题目,本能的你会使用排序(数字文字我们常常需要排序),排序后可以来判断是否数字成对出现,思路很明显,但是排序的算法上限是 O(nlogn),不符合题目要求;

    学习了强大的异或,我们可以轻松的使用它的特性来完成这道题目: (1)A ^ A = 0; (2)异或满足交换律、结合律; 所有假设有数组:A B C B C D A 使用异或:

    1
    2
    3
    4
    5
    
    A ^ B ^ C ^ B ^ C ^ D ^ A
    = A ^ A ^ B ^ B ^ C ^ C ^ D
    = 0 ^ 0 ^ 0 ^ D
    = 0 ^ D
    = D
    

    是不是很神奇?时间复杂度为O(n),当然是线性的,空间复杂度O(1)

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    
    class Solution {
    public:
        int singleNumber(int A[], int n) {
            //特殊情况1,2  
            if(n<=0) return -1;
            if(n==1) return A[0];
    
            int result = 0;
            for (int i = 0; i < n; i ++) {
                result = result ^ A[i];
            }
            return result;
        }
    };
    

    接下来让我们增加一些难度:

    题目:一个整型数组里除了个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字?

    思路: 第一步:肯定还是像我们上面的解法一样,所有数进行异或,不过最终得到的结果是 a 和 b(假设 a 和 b 是落单的数字)两个值的异或结果 aXORb,没有直接得到 a 和 b 的值;

    第二步:想办法得到 a 或者 b,假设 aXORb 为 00001001(F肯定不为0),根君 aXORb 的值我们发现,值为1的位(比如从右向左第一位)表示在此位上 a 和 b 的值不同;所以,根据这个特点,我们找出来所有第一位为1的数进行异或,得到的就是 a 或者 b;

    第三步:aXORb = a ^ b,假设我们已经找到了 a,根据异或特性,我们知道,b = aXORb ^ a;这样我们就可以找出 b;所以我们只需要循环两次;

    这样我们的时间复杂度是 O(n),空间复杂度是 O(1) 代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    
    #include <iostream>
    #include <assert.h>
    using namespace std;
    
    int getFirstOneBit(int num) //输出 num 的低位中的第一个 1 的位置  
    {
        return num & ~(num - 1);  // num 与 -num 相与找到
    }
    
    void findTwo(int *array, int length){
        int aXORb = 0;
        int firstOneBit = 0;
        int a = 0;
        int b = 0;
        for (int i = 0; i < length; i++) {
            aXORb ^= array[i];
        }
        assert(aXORb != 0); //保证题目要求,有两个single的数字
        firstOneBit = getFirstOneBit(aXORb);
        for (int i = 0; i < length; ++i) {
            if(array[i] & firstOneBit) {
                a ^= array[i];
            }
        }
        b = aXORb ^ a;
        cout << "a: " << a << endl;
        cout << "b: " << b << endl;
    }
    
    
    int main()
    {
        int array1[] = {2, 5, 8, 2, 5, 8, 6, 7};
        findTwo(array1, 8);
        return 0;
    }
    

    接下来让我们再增加一些难度:

    题目:一个整型数组里除了个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字?

    思路

    第一步:肯定还是像我们上面的解法一样,所有数进行异或,不过最终得到的结果是 a、b 和 c(假设 a、b 和 c 是落单的数字)三个值的异或结果 aXORbXORc,没有直接得到 a、b 和 c 的值;

    第二步:想办法得到 a、b 和 c 中的一个,让偶们把问题简化一下;

    假设一个数组中有3个不同的数字 a、b 和 c,已知 aXORbXORc = a ^ b ^ c ,求 a、b 和 c 。

    思路: 1. 根据题目 aXORbXORc ^ a = b ^ c; aXORbXORc ^ b = a ^ c; aXORbXORc ^ c = a ^ b; 因为:(b ^ c) ^ (a ^ c) ^ (a ^ b) = 0; 所以:(aXORbXORc ^ a) ^ (aXORbXORc ^ b) ^ (aXORbXORc ^ c) = 0;

    1. 下一步是关键: 假设 X ^ Y ^ Z = 0,则 X Y Z 三个数的低位第一位为1的位置两个相同,一个不同; 比如 X: 00001000, Y: 00000100, Z: 00001100 Y和Z的低位第一位都是00000100, X的低位第一位是00001000; 这一步可以使用倒推法证明: 已知:三个数的低位第一位为1的位置有三种情况,一种就是全相同,一种就是两个不同,一个不同,一种就是三个不同; (1)如果是全相同,则 X ^ Y ^ Z != 0 (1 ^ 1 ^ 1 = 1),与前提X ^ Y ^ Z = 0矛盾,不成立; (2)如果三个不同,则 X ^ Y ^ Z != 0 (1 ^ 0 ^ 0 = 1),与前提X ^ Y ^ Z = 0矛盾,不成立; 所以结果是:两个不同,一个不同

    2. (aXORbXORc ^ a) ^ (aXORbXORc ^ b) ^ (aXORbXORc ^ c) = 0; 所以三个数(aXORbXORc ^ a)、(aXORbXORc ^ b) 和 (aXORbXORc ^ c) 的低位第一位为1的位置两个相同,一个不同;那么我们获取到这三个数的低位第一位为1的位置后,进行异或并取低位第一位为1的位置,就可以找到三个中“一个不同”的低位第一位为1的位置,假设这个值为 firstOneBit。

    3. 遍历这三个数(aXORbXORc ^ a)、(aXORbXORc ^ b) 和 (aXORbXORc ^ c),如果发现某个数异或 aXORbXORc 等于 firstOneBit,这个数就是“一个不同”的那个数;

    4. 找到了一个数,剩下的两个数,我们就可以通过上面的方法找出来;

    第三步:完成了第二步的简化题,我们回到我们的问题,我们的问题比简化的问题多了一个成对的干扰数据,我们可以使用异或要去除干扰数据(记住,我们这个题目都是用异或i去除干扰数据的);

    这样我们的时间复杂度还是 O(n),空间复杂度是 O(1)

    代码如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    
    #include <iostream>
    #include <assert.h>
    using namespace std;
    
    int getFirstOneBit(int num) //输出 num 的低位中的第一个 1 的位置  
    {
        return num & ~(num - 1);  // num 与 -num 相与找到
    }
    
    void findTwo(int *array, int length){
        int aXORb = 0;
        int firstOneBit = 0;
        int a = 0;
        int b = 0;
        for (int i = 0; i < length; i++) {
            aXORb ^= array[i];
        }
        assert(aXORb != 0); //保证题目要求,有两个single的数字
        firstOneBit = getFirstOneBit(aXORb);
        for (int i = 0; i < length; ++i) {
            if(array[i] & firstOneBit) {
                a ^= array[i];
            }
        }
        b = aXORb ^ a;
        cout << "a: " << a << endl;
        cout << "b: " << b << endl;
    }
    
    int findOne(int *array, int length) {
        int aXORbXORc = 0;
        int c = 0;
        int firstOneBit = 0;
        for (int i = 0; i < length; ++i) {
            aXORbXORc ^= array[i];
        }
    
        for (int i = 0; i < length; ++i) {
            firstOneBit ^= getFirstOneBit(aXORbXORc ^ array[i]); //使用异或会排除掉不相干的元素
        }
        // firstOneBit = getFirstOneBit(a ^ b) ^ getFirstOneBit(a ^ c) ^ getFirstOneBit(b ^ c);
    
        firstOneBit = getFirstOneBit(firstOneBit); //获取到最低位下面要用
    
        for (int i = 0; i < length; ++i) {
            if (getFirstOneBit(aXORbXORc ^ array[i]) == firstOneBit) {
                c ^= array[i]; //使用异或会排除掉不相干的元素
            }
        }
        cout << "c: " << c << endl;
        return c;
    }
    
    int main()
    {
        int array1[] = {2, 5, 8, 2, 5, 8, 6, 7, 1};
        int c = findOne(array1, 9);
        int array2[] = {2, 5, 8, 2, 5, 8, 6, 7, 1, c}; //为了更好重用函数,我重新定义了一个数组让大家理解
        findTwo(array2, 10);
        return 0;
    }
    

    写这篇文档参考了《离散数学与应用》课本,参考了别人多个博客,如果我参考了你的博客,但没有注明出处,请联系告知,有错误的地方,希望可以指出来,也希望大家有更多的补充,非常感谢。

    参考:

    http://zh.wikipedia.org/wiki/%E9%80%BB%E8%BE%91%E5%BC%82%E6%88%96

    http://yjq24.blogbus.com/logs/41863963.html

    http://wzw19191.blog.163.com/blog/static/131135470200992610551971/

    http://kapok.blog.51cto.com/517862/129941

    http://blog.csdn.net/huxian370/article/details/8024416

    http://www.cnblogs.com/Ivony/archive/2009/07/23/1529254.html

    http://blog.chinaunix.net/uid-20937170-id-3407361.html

    http://blog.csdn.net/yfkiss/article/details/11775569

    http://blog.sina.com.cn/s/blog_88c9ddc50101810p.html

    http://blog.csdn.net/pathuang68/article/details/7567027

    http://blog.csdn.net/qingen1/article/details/12656763

    展开全文
  • 异或运算异或运算可以看做是没有进位的加法,按位异或运算,相同为0,不同为1。0 ^ 0 = 00 ^ 1 = 11 ^ 0 = 11 ^ 1 = 0观察运算结果我们发现,当与0做异或运算时,另一元值不变;而与1做异或运算时,另一元值值取反。...

    异或运算

    异或运算可以看做是没有进位的加法,按位异或运算,相同为0,不同为1。

    0 ^ 0 = 0

    0 ^ 1 = 1

    1 ^ 0 = 1

    1 ^ 1 = 0

    观察运算结果我们发现,当与0做异或运算时,另一元值不变;而与1做异或运算时,另一元值值取反。

    用途

    根据以上异或运算的特征,可以有以下用途,除方便直观外,运算性能也更加优异。

    1)变量重置0

    假设有一个变量15,二进制表示为0000 1111

    0000 1111 ^ 0000 1111 = 0000 0000

    a = 0000 1111

    a = a ^ a

    结论:同变量本身异或运算,可以将变量重置0。

    2)指定位置取反

    假设有一个变量15,二进制表示为0000 1111,将第3,4,8位取反。

    0000 1111 ^ 1000 1100 = 1000 0011

    结论:同指定取反位为1,其他位为0的变量进行异或运算,可以将指定位置取反。

    取反后的结果,同原指定取反变量异或,可以还原变量:

    1000 0011 ^ 1000 1100 = 0000 1111(15)

    3)加密解密

    假设有一个变量15,二进制表示为0000 1111,密码子为0101 0101。

    加密:0000 1111 ^ 0101 0101 = 0101 1010

    加密后结果是90。

    将加密后结果同密码子异或,可以进行解密

    0101 1010 ^ 0101 0101 = 0000 1111

    解密后结果是15。

    4)二值交换

    假设两个变量:a = 15(0000 1111), b= 23(0001 0111),将两个变量交换。

    1、a = a ^ b = 0000 1111 ^ 0001 0111 = 0001 1000

    2、b = b ^ a = 0001 0111 ^ 0001 1000 = 0000 1111(15)

    3、a = a ^ b = 0001 1000 ^ 0000 1111 = 0001 0111(23)

    结论:二值交换实际上是利用了加密解密的特性。

    1、a和b异或,可以把结果x看作是a、b互为密码子进行加密。

    2、将x,同b(原值)异或,也就是把b作为密码子,因此可以还原a,赋值给b。

    3、将x,同b(此时为a)异或,也就是把b(此时为a)作为密码子,因此还原出的值为原b,赋值给a。交换结束。

    5)判断两值是否相等

    利用同变量本身异或运算,可以将变量重置0的特性。

    假设:a = 0000 1111,b = 0000 1111,则 a ^ b == 0

    假设:a = 0000 1111,b = 0000 0001,则 a ^ b != 0

    结论:当两个变量相等时,异或结果为0。

    fec178d9875c8ebecbdcdf91bb5f522f.png
    展开全文
  • 什么是异或_异或运算异或运算的作用 异或,是一个数学运算符,英文为exclusive OR,缩写为xor,应用于逻辑运算。异或的数学符号为“⊕”,计算机符号为“xor”。其运算法则为:  a⊕b = (¬a ∧ b) ∨ (a ∧...

    什么是异或_异或运算及异或运算的作用

    异或,是一个数学运算符,英文为exclusive OR,缩写为xor,应用于逻辑运算。

    异或的数学符号为“⊕”,计算机符号为“xor”。其运算法则为:

      a⊕b = (¬a ∧ b) ∨ (a ∧¬b)

    如果a、b两个值不相同,则异或结果为1。如果a、b两个值相同,异或结果为0。

    异或也叫半加运算,其运算法则相当于不带进位的二进制加法:

    二进制下用1表示真,0表示假,则异或的运算法则为:0⊕0=0,1⊕0=1,0⊕1=1,1⊕1=0(同为0,异为1),

    这些法则与加法是相同的,只是不带进位。

      异或略称为XOR、EOR、EX-OR

      程序中有三种演算子:XOR、xor、⊕。

      使用方法如下

      z = x ⊕ y

      z = x xor y

    异或运算的作用

    参与运算的两个值,如果两个相应bit位相同,则结果为0,否则为1。

    即:

    0^0 = 0,

    1^0 = 1,

    0^1 = 1,

    1^1 = 0

    按位异或的3个特点:

    (1) 0^0=0,0^1=1 0异或任何数=任何数

    (2) 1^0=1,1^1=0 1异或任何数-任何数取反

    (3) 任何数异或自己=把自己置0

    按位异或的几个常见用途:

    (1) 使某些特定的位翻转

    例如对数10100001的第2位和第3位翻转,则可以将该数与00000110进行按位异或运算。

    10100001^00000110 = 10100111

    (2) 实现两个值的交换,而不必使用临时变量。

      例如交换两个整数a=10100001,b=00000110的值,可通过下列语句实现:

      a = a^b;   //a=10100111

      b = b^a;   //b=10100001

      a = a^b;   //a=00000110

      (3) 在汇编语言中经常用于将变量置零:

      xor a,a

      (4) 快速判断两个值是否相等

      举例1: 判断两个整数a,b是否相等,则可通过下列语句实现:

      return ((a ^ b) == 0)

      举例2: Linux中最初的ipv6_addr_equal()函数的实现如下:

      staTIc inline int ipv6_addr_equal(const struct in6_addr *a1, const struct in6_addr *a2)

      {

      return (a1-》s6_addr32[0] == a2-》s6_addr32[0] &&

      a1-》s6_addr32[1] == a2-》s6_addr32[1] &&

      a1-》s6_addr32[2] == a2-》s6_addr32[2] &&

      a1-》s6_addr32[3] == a2-》s6_addr32[3]);

      }

      可以利用按位异或实现快速比较, 最新的实现已经修改为:

      staTIc inline int ipv6_addr_equal(const struct in6_addr *a1, const struct in6_addr *a2)

      {

      return (((a1-》s6_addr32[0] ^ a2-》s6_addr32[0]) |

      (a1-》s6_addr32[1] ^ a2-》s6_addr32[1]) |

      (a1-》s6_addr32[2] ^ a2-》s6_addr32[2]) |

      (a1-》s6_addr32[3] ^ a2-》s6_addr32[3])) == 0);

      }

      5 应用通式:

      对两个表达式执行按位异或。

      result = expression1 ^ expression2

      参数

      result

      任何变量。

      expression1

      任何表达式。

      expression2

      任何表达式。

      说明

      ^ 运算符查看两个表达式的二进制表示法的值,并执行按位异或。该操作的结果如下所示:

      0101 (expression1)1100 (expression2)----1001 (结果)当且仅当只有一个表达式的某位上为 1 时,结果的该位才为 1。否则结果的该位为 0。

      只能用于整数

      下面这个程序用到了“按位异或”运算符:

      class E

      { public staTIc void main(String args[ ])

      {

      char a1=‘十’ , a2=‘点’ , a3=‘进’ , a4=‘攻’ ;

      char secret=‘8’ ;

      a1=(char) (a1^secret);

      a2=(char) (a2^secret);

      a3=(char) (a3^secret);

      a4=(char) (a4^secret);

      System.out.println(“密文:”+a1+a2+a3+a4);

      a1=(char) (a1^secret);

      a2=(char) (a2^secret);

      a3=(char) (a3^secret);

      a4=(char) (a4^secret);

      System.out.println(“原文:”+a1+a2+a3+a4);

      }

      }

      就是加密啊解密啊

      char类型,也就是字符类型实际上就是整形,就是数字。

      计算机里面所有的信息都是整数,所有的整数都可以表示成二进制的,实际上计算机只认识二进制的。

      位运算就是二进制整数运算啦。

      两个数按位异或意思就是从个位开始,一位一位的比。

      如果两个数相应的位上一样,结果就是0,不一样就是1

      所以111^101=010

      那加密的过程就是逐个字符跟那个secret字符异或运算。

      解密的过程就是密文再跟同一个字符异或运算

      010^101=111

      至于为什么密文再次异或就变原文了,这个稍微想下就知道了。。

      异或运算:按位异或运算符

      首先异或表示当两个数的二进制表示,进行异或运算时,当前位的两个二进制表示不同则为1相同则为0.该方法被广泛推广用来统计一个数的1的位数!

      参与运算的两个值,如果两个相应bit位相同,则结果为0,否则为1。

      即:

      0^0 = 0,

      1^0 = 1,

      0^1 = 1,

      1^1 = 0

      按位异或的3个特点:

      (1) 0^0=0,0^1=1 0异或任何数=任何数

      (2) 1^0=1,1^1=0 1异或任何数-任何数取反

      (3) 任何数异或自己=把自己置0

      按位异或的几个常见用途:

      (1) 使某些特定的位翻转

      例如对数10100001的第2位和第3位翻转,则可以将该数与00000110进行按位异或运算。

      10100001^00000110 = 10100111

      (2) 实现两个值的交换,而不必使用临时变量。

      例如交换两个整数a=10100001,b=00000110的值,可通过下列语句实现:

      a = a^b;   //a=10100111

      b = b^a;   //b=10100001

      a = a^b;   //a=00000110

      位运算

      位运算时把数字用二进制表示之后,对每一位上0或者1的运算。理解位运算的第一步是理解二进制。二进制是指数字的每一位都是0或者1.比如十进制的2转化为二进制之后就是10。

      其实二进制的运算并不是很难掌握,因为位运算总共只有5种运算:与、或、异或、左移、右移。如下表:

      

      左移运算:

      左移运算符m《《n表示吧m左移n位。左移n位的时候,最左边的n位将被丢弃,同时在最右边补上n个0.比如:

      

     

      右移运算:

      右移运算符m》》n表示把m右移n位。右移n位的时候,最右边的n位将被丢弃。但右移时处理最左边位的情形要稍微复杂一点。这里要特别注意,如果数字是一个无符号数值,则用0填补最左边的n位。如果数字是一个有符号数值,则用数字的符号位填补最左边的n位。也就是说如果数字原先是一个正数,则右移之后再最左边补n个0;如果数字原先是负数,则右移之后在最左边补n个1.下面是堆两个8位有符号数作右移的例子:

      

     

      关于移位的运算有这样的等价关系:把整数右移一位和把整数除以2在数学上是等价的。

      

     

      计算机内部只识别1、0,十进制需变成二进制才能使用移位运算符《《,》》 。

      int j = 8;

      p = j 《《 1;

      cout《《p《《endl;

      在这里,8左移一位就是8*2的结果16 。

      移位运算是最有效的计算乘/除乘法的运算之一。

      按位与(&)其功能是参与运算的两数各对应的二进制位相与。只有对应的两个二进制位均为1时,结果位才为1,否则为0 。参与运算的数以补码方式出现。

      先举一个例子如下:

      题目:请实现一个函数,输入一个正数,输出该数二进制表示中1的个数。

      

     

      这里用到了这样一个知识点:把一个整数减去1,再和原整数做与运算,会把该整数最右边一个1变成0 。 那么一个整数的二进制表示中有多少个1,就可以进行多少次这样的操作。

      总结:把一个整数减去1之后再和原来的整数做位与运算,得到的结果相当于是把整数的二进制表示中的最右边一个1变成0 。

      位运算的应用可以运用于很多场合:

      清零特定位(mask中特定位置0,其它位为1 , s = s & mask)。

      取某数中指定位(mask中特定位置,其它位为0, s = s & mask)。

      举例:输入两个整数m和n,计算需要改变m的二进制表示中的多少位才能得到n。

      解决方法:第一步,求这两个数的异或;第二步,统计异或结果中1的位数。

      

     

      接下来我们再举一例,就可以更好的说明移位运算了:用一条语句判断一个整数是不是2的整数次方。

      解决方法:一个整数如果是2的整数次方,那么它的二进制表示中有且只有一位是1,而其它所有位都是0 。 根据前面的分析,把这个整数减去1后再和它自己做与运算,这个整数中唯一的1就变成0了。

      解答:!(x & (x - 1))

    展开全文
  • 异或运算两者相等为0,不等为11^1=0, 1^0=1, 0^1=1, 0^0=0 下面是详细的解释: 位运算 位运算的运算分量只能是整型或字符型数据,位运算把运算对象看作是由二进位组成的位串信息,按位完成指定的运算,得到位串信息...
  • 异或运算的性质:异或运算是基于二进制的位运算,采用符号XOR或者^来表示,运算规则是就与二进制,如果是同值取0、异值取1。简单的理解就是不进位加法,例如1+1=0,0+0=0,1+0=0;性质:交换律 可以任意交换运算因子...

    异或运算的性质:

    异或运算是基于二进制的位运算,采用符号XOR或者^来表示,运算规则是就与二进制,如果是同值取0、异值取1。

    简单的理解就是不进位加法,例如1+1=0,0+0=0,1+0=0;

    性质:

    1. 交换律 可以任意交换运算因子,结果不变。
    2. 结合律 (a^b)^c=a^(a^c)
    3. 对于任何数x,都有x^x=0,x^0=x,同自己求异或运算为0,同0求异或运算结果为自己
    4. 自反性,A^B^B=A^0=A。这个性质可以用来求哪一个数为一个

    用法实例:

    例一:在不引入第三个变量的情况下,两个变量的值(整数)

    //交换a、b的值
    a=a^b
    b=a^b
    a=a^b

    例二:判断奇数偶数更简单更高效的做法

    //这个实际考的不多, 太简单
    //思路:奇数的二进制最低为一定为1,偶数的二进制最低位一定为0,
    a^1==1?偶数:奇数

    例三:找出唯一一个成对的数

    题干:1-1000这1000个数放在含有1001个元素的数组中,只有唯一的一个元素值重复,其它均只出现 一次。每个数组元素只能访问一次,设计一个算法,将它找出来;不用辅助存储空 间,能否设计一个算法实现?

    第一种解题思路:将所有的数加起来减去(1+2+……+1000)。但是这个有可能导致内存溢出

    //第二种思路:
    将所有的值异或运算,结果再与(1^2^3……^1000)异或运算
    结果相当于(1^1^2^2……1000^1000^k)最终的结果就是k
    

    例题五:找出唯一落单的那个数字(也就是仅仅出现一次的那个数)

    结果=a[0]^a[1]^...^a[n-1]
    

    例题六:(难度增加)找出数组中落单的那两个数

    题目:一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。
    package test.nowcoder;
    
    import java.util.ArrayList;
    import java.util.List;
    
    /**
     * @Autre beyond
     * @Data 2019/10/19
     * 这个案例相比之前,难度有所跨越,它综合运用到了几个知识:
     *
     * 异或运算
     * 相同的数在某位上一定相同
     * 朴素的分治,将数分为两类,再分别求解
     * 移位运算
     * 与运算:判断某位是否为0这也可以出个题了
     * 
     */
    public class TowNumOdd {
        public static void main(String[] args) {
            int [] arr={1,2,3,3,4,4,5,6,5,6};
            //先求总的
            int n=0;
            int temp=0;
            for (int i = 0; i <arr.length ; i++) {
                temp^=arr[i];
            }
    
           while (true){
               if ((temp&(1<<n++))==1){
                break;
               }
           }
           /*这个得出N位为整数的第一个非0(即1)位的方法很巧妙:和1做按位与运算,如果位上为1结果为1,N求出;
    
    如果位上为0则结果为0,将1移动到下一位继续判断*/
    
           // 循环最后多加了1
           n--;
    
            List<Integer> num1=new ArrayList<>();
            List<Integer> num2=new ArrayList<>();
    
            for (int i = 0; i <arr.length ; i++) {
                if ((arr[i]&(1<<n))==0) {
                    num1.add(arr[i]);
                }else {
                    num2.add(arr[i]);
                }
            }
            int arr1=0,arr2=0;
            for (int i = 0; i <num1.size() ; i++) {
                arr1^=num1.get(i);
    
            }
            for (int i = 0; i <num2.size() ; i++) {
                arr2^=num2.get(i);
    
            }
            System.out.println(arr1+"+"+arr2);
    
        }
    }

    例题七:找连续自然数中跑丢的两个数

    题目为:给你1-1000个连续自然数,然后从中随机去掉两个,再打乱顺序,要求只遍历一次,求出被去掉的两个数。

    思路和例题6一样了,先用(1^2^3...^1000)与去掉的异或运算,之后就可以用例题6计算了。

    例题八:(再次升级)找到落单的三个数

    一个数组中有三个数字a、b、c只出现一次,其他数字都出现了两次。请找出三个只出现一次的数字。
    寻找数组中只出现一次的三个数 | 蓝桥软件学院lanqiao.coding.me

    例九: 思考题:不用判断语句,求整数的绝对值

    一般思考:正数返回本身,负数取反+1,但这涉及到判定数是正的还是负的
    提示:带符号右移31位,正数变为0,负数变为-1(1111 1111 … 1111 1111),任何数和-1做“异或”运算相当于取反……只能说这么多了
       public static void main(String[] args) {
          int number;
    Scanner in = new Scanner(System.in);
     number = in.nextInt();
     /*
         * >> 右移,高位补符号位
         * >>> 无符号右移,高位补0
         * ^ 异或,相同为0,不同为1
         */
    System.out.println(number + "的绝对值是:" + ((number^(number>>31))+(number>>31)));
    
        }
    展开全文
  • 参加运算的两个对象,按二进制位进行运算。 进制转换地址:http://tool.oschina.net/hexconvert/ 一:与运算符(&) 预算规则: 0&0=0;0&1=0;1&0=0;1&1=1 即:两个同时为1,结果为1,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,700
精华内容 5,880
关键字:

异或运算