位运算异或

目录

一、知识点

1.异或运算符

2.应用

（1）标记位取反

（2）变量交换

（3）出现奇数次的数

二、习题

1.136. 只出现一次的数字 - 力扣（LeetCode）

2.190. 颠倒二进制位 - 力扣（LeetCode）

3.461. 汉明距离 - 力扣（LeetCode）

4.1486. 数组异或操作 - 力扣（LeetCode）

5.477. 汉明距离总和 - 力扣（LeetCode）

6.1720. 解码异或后的数组 - 力扣（LeetCode）

---

一、知识点

1.异或运算符

• 异或运算符有两个操作数，表示为 x ^ y
• 对操作数的每一位进行运算，两个数相同结果为0，不同为1.
• 任何一个数和0的异或结果一定是本身
• 满足交换律和结合律

左操作数	右操作数	结果
0	0	0
0	1	1
1	0	1
1	1	0

2.应用

（1）标记位取反

给定一个数，将它的低位数起的第四位取反，0变1，1变0

x^0b1000
//和0异或的结果是本身，所以末三位000，0^1=1,1^1=0,满足条件，用异或。

（2）变量交换

给定两个数a和b，用异或运算交换他们的值

a=a^b;
b=a^b;
a=a^b;

解释：相当于b=a^b^b=a //异或满足交换律和结合律b=a^(b^b)  ,我们知道两个一样的数异或为0，而任何与0异或的数，都为本身，所以b=a;

a=a^b^(a^b^b)=a^b^a=(a^a)^b=b

（3）出现奇数次的数

输入n个数，其中只有一个数出现了奇数次，其它所有数都出现了偶数次，求这个出现了奇数次的数

解释：两个一样的数异或结果为0，也就是所有出现偶数次的数异或结果为0，把n个数异或一下，得到的数就是一个出现奇数次的数。

二、习题

1.136. 只出现一次的数字 - 力扣（LeetCode）

class Solution {
public:
    int singleNumber(vector<int>& nums) {
//根据异或的性质，两个一样的数异或结果为0，所有出现偶数次的数异或都为0，把n个数都异或，最后得到的数就是出现奇数次数的数
int ans=0;
for(int i=0;i<nums.size();i++)
{
ans^=nums[i];
}
return ans;
    }
};

2.190. 颠倒二进制位 - 力扣（LeetCode）

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t rev = 0;//与0异或为本身。
        for (int i = 0; i < 32 && n > 0; ++i) {
            rev ^= ((n & 1) << (31 - i));//n&1判断n的奇偶性，即看n的末位为0还是1
            n >>= 1;
        }
        return rev;
    }
};

3.461. 汉明距离 - 力扣（LeetCode）

class Solution {
public:
    int hammingDistance(int x, int y) {
int sum=0;
x=x^y;
while(x)
{
    sum+=x&1;
    x>>=1;
}
return sum;
    }
};

4.1486. 数组异或操作 - 力扣（LeetCode）

class Solution {
public:
    int xorOperation(int n, int start) {
int x=0;
for(int i=0;i<n;i++)
{
    x^=start+2*i;
}
return x;
    }
};

5.477. 汉明距离总和 - 力扣（LeetCode）

class Solution {
public:
//对汉明距离有贡献的只有1 ^ 0 ，若数组的3个数在某同一位上的数分别是0,1,1  那么这个汉明距离的总和为2. 即 1*2。
//所有位上 0的个数 * 1的个数 的和 即是汉明距离的个数。

int totalHammingDistance(vector<int>& nums) {
int sum=0,n=nums.size();

for(int i=0;i<30;i++)//nums[i]<=10^9.  2^30>10^9  枚举到29即可。   i<32也可以通过
{
   int c=0;
   for(int num:nums)
   {
   c+=(num>>i)&1;//取出第i位的值，计算1的个数。
   }
   sum+=c*(n-c);
}

return sum;
    }
};

6.1720. 解码异或后的数组 - 力扣（LeetCode）

class Solution {
public:
//arr[0]^arr[1]=encoded[0];
//两边同时异或arr[0].
//得到arr[1]=encoded[0]^arr[0];
//以此类推。
//arr[i]=encoded[i-1]^arr[i-1];

vector<int> decode(vector<int>& encoded, int first) {
int n=encoded.size()+1;
vector<int> arr(n);
arr[0]=first;
for(int i=0;i<n-1;i++) //最大下标是encoded.size()
{
    arr[i+1]=encoded[i]^arr[i];
}

return arr;
    }
};

参考专栏：

(109条消息) 《算法零基础100讲》(第46讲) 位运算 (异或) 入门_英雄哪里出来的博客-CSDN博客