Bit operation XOR

Catalog

One 、 Knowledge point

1. Exclusive or operator

2. application

（1） The flag bit is reversed

（2） Variable exchange

（3） An odd number of times

Two 、 exercises

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 ：

(109 Bar message ) 《 Algorithm zero basis 100 speak 》( The first 46 speak ) An operation ( Exclusive or ) introduction _ Where did the hero come out of the blog -CSDN Blog