当前位置:网站首页>Bit operation XOR
Bit operation XOR
2022-07-06 07:17:00 【Yang Yi】
Catalog
1.136. A number that appears only once - Power button (LeetCode)
2.190. Invert binary bit - Power button (LeetCode)
3.461. Hamming distance - Power button (LeetCode)
4.1486. Array XOR operation - Power button (LeetCode)
5.477. The sum of Hamming distances - Power button (LeetCode)
6.1720. Decode the XOR array - Power button (LeetCode)
One 、 Knowledge point
1. Exclusive or operator
- The XOR operator has two operands , Expressed as x ^ y
- Operate on each bit of the operand , If the two numbers are the same, the result is 0, Different for 1.
- Any number and 0 The XOR result of must be In itself
- Satisfy the law of exchange and the law of union
Left operand | Right operands | result |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
2. application
(1) The flag bit is reversed
Give a number , Reverse the fourth digit from its low number ,0 change 1,1 change 0
x^0b1000
// and 0 The result of XOR is itself , So the last three 000,0^1=1,1^1=0, Meet the conditions , Using XOR .
(2) Variable exchange
Given two numbers a and b, Exchange their values with XOR
a=a^b;
b=a^b;
a=a^b;
explain : amount to b=a^b^b=a // XOR satisfies commutative law and associative law b=a^(b^b) , We know that two identical numbers are exclusive or 0, And any and 0 The number of exclusive or , All for themselves , therefore b=a;
a=a^b^(a^b^b)=a^b^a=(a^a)^b=b
(3) An odd number of times
Input n Number , Only one of them appears odd times , All other numbers appear an even number of times , Find the number that appears odd times
explain : The result of two identical numbers exclusive or is 0, That is, the result of all the number XORs that occur an even number of times is 0, hold n Number XOR , The resulting number is a number that occurs an odd number of times .
Two 、 exercises
1.136. A number that appears only once - Power button (LeetCode)
class Solution {
public:
int singleNumber(vector<int>& nums) {
// According to the nature of the xor , The result of two identical numbers exclusive or is 0, All number XORs that occur an even number of times are 0, hold n The numbers are exclusive or , The final number is the number of odd numbers
int ans=0;
for(int i=0;i<nums.size();i++)
{
ans^=nums[i];
}
return ans;
}
};
2.190. Invert binary bit - Power button (LeetCode)
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t rev = 0;// And 0 XOR is itself .
for (int i = 0; i < 32 && n > 0; ++i) {
rev ^= ((n & 1) << (31 - i));//n&1 Judge n Parity , That is to say n The last place is 0 still 1
n >>= 1;
}
return rev;
}
};
3.461. Hamming distance - Power button (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. Array XOR operation - Power button (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. The sum of Hamming distances - Power button (LeetCode)
class Solution {
public:
// Only 1 ^ 0 , If the array 3 The numbers on the same bit are 0,1,1 Then the sum of the Hamming distance is 2. namely 1*2.
// On all positions 0 The number of * 1 The number of And That is, the number of Hamming distance .
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 Enumerate to 29 that will do . i<32 It can also be done through
{
int c=0;
for(int num:nums)
{
c+=(num>>i)&1;// Take out No i The value of a , Calculation 1 The number of .
}
sum+=c*(n-c);
}
return sum;
}
};
6.1720. Decode the XOR array - Power button (LeetCode)
class Solution {
public:
//arr[0]^arr[1]=encoded[0];
// Simultaneous XOR on both sides arr[0].
// obtain arr[1]=encoded[0]^arr[0];
// And so on .
//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++) // The maximum subscript is encoded.size()
{
arr[i+1]=encoded[i]^arr[i];
}
return arr;
}
};
Reference column :
边栏推荐
- On the world of NDK (2)
- 这个高颜值的开源第三方网易云音乐播放器你值得拥有
- NFT on fingertips | evaluate ambire on G2, and have the opportunity to obtain limited edition collections
- Project GFS data download
- 作者已死?AI正用藝術征服人類
- Lesson 12 study notes 2022.02.11
- CDN acceleration and cracking anti-theft chain function
- leetcode704. 二分查找(查找某个元素,简单,不同写法)
- leetcode841. 钥匙和房间(中等)
- leetcode1020. Number of enclaves (medium)
猜你喜欢
Establishment and operation of cloud platform open source project environment
Internal and external troubles of "boring ape" bayc
作者已死?AI正用艺术征服人类
Solution to the problem of breakthrough in OWASP juice shop shooting range
Hydra common commands
leetcode1020. Number of enclaves (medium)
Leetcode 78: subset
mysql如何合并数据
Win10 64 bit Mitsubishi PLC software appears oleaut32 DLL access denied
Wechat brain competition answer applet_ Support the flow main belt with the latest question bank file
随机推荐
Bio model realizes multi person chat
Top test sharing: if you want to change careers, you must consider these issues clearly!
C - Inheritance - hidden method
What is the biggest problem that fresh e-commerce is difficult to do now
Compile, connect -- notes-2
OpenJudge NOI 2.1 1661:Bomb Game
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
配置树莓派接入网络
word中如何删除某符号前面或后面所有的文字
Jerry needs to modify the profile definition of GATT [chapter]
[server data recovery] case of offline data recovery of two hard disks of IBM server RAID5
navicat如何导入MySQL脚本
Win10 64 bit Mitsubishi PLC software appears oleaut32 DLL access denied
mysql如何合并数据
leetcode59. 螺旋矩阵 II(中等)
树莓派3B更新vim
#systemverilog# 可綜合模型的結構總結
Résumé de la structure du modèle synthétisable
Markdown 中设置图片图注
Kubernetes cluster builds ZABBIX monitoring platform