当前位置:网站首页>位运算异或
位运算异或
2022-07-06 07:16:00 【阳懿】
目录
1.136. 只出现一次的数字 - 力扣(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;
}
};
参考专栏:
边栏推荐
- 树莓派串口登录与SSH登录方法
- 巴比特 | 元宇宙每日必读:中国互联网企业涌入元宇宙的群像:“只有各种求生欲,没有前瞻创新的雄心”...
- OpenJudge NOI 2.1 1661:Bomb Game
- Uncaught typeerror: cannot red properties of undefined (reading 'beforeeach') solution
- 开源的网易云音乐API项目都是怎么实现的?
- How to find a medical software testing institution? First flight software evaluation is an expert
- Go learning --- use reflection to judge whether the value is valid
- Zhongqing reading news
- Configure raspberry pie access network
- 3. Business and load balancing of high architecture
猜你喜欢
Supporting title of the book from 0 to 1: ctfer's growth road (Zhou Geng)
Kubernetes cluster builds ZABBIX monitoring platform
“无聊猿” BAYC 的内忧与外患
Multi attribute object detection on rare aircraft data sets: experimental process using yolov5
mysql如何合并数据
Cookie Technology & session Technology & ServletContext object
Top test sharing: if you want to change careers, you must consider these issues clearly!
navicat如何导入MySQL脚本
Solution to the problem of breakthrough in OWASP juice shop shooting range
树莓派串口登录与SSH登录方法
随机推荐
leetcode841. 钥匙和房间(中等)
C语言 简单易懂的高精度加法
Missing monitoring: ZABBIX monitors the status of Eureka instance
Chrome view page FPS
【mysql学习笔记30】锁(非教程)
杰理之如若需要大包发送,需要手机端修改 MTU【篇】
Supervisor usage document
How are the open source Netease cloud music API projects implemented?
Seriously recommend several machine learning official account
Simple and understandable high-precision addition in C language
supervisor 使用文档
Résumé de la structure du modèle synthétisable
JDBC learning notes
Short video, more and more boring?
【JDBC】快速入门教程
The differences and advantages and disadvantages between cookies, seeion and token
OpenJudge NOI 2.1 1661:Bomb Game
leetcode6109. 知道秘密的人数(中等,周赛)
TypeScript void 基础类型
Development of entity developer database application