The wonderful use of XOR (C language)

Bitwise XOR Is an operation on a binary bit ：

One sentence summary , Namely A fellow 0, Different from 1.
0 ^ 0 = 0
1 ^ 1 = 0
0 ^ 1 = 1
1 ^ 0 = 1

What is the use of XOR ？ It has a wonderful use . What's the use ？ It has the following wonderful functions .

Let's first review The operational nature of XOR ：

0 ^ n = n
n ^ n = 0
a ^ b = b ^ a
(a ^ b) ^ c = a ^ (b ^ c)
among a, b, c, n All are integers .

Converting the above into text is ：

0 Exclusive or with any integer , The result is the original integer
The result of any integer exclusive or with itself is 0
XOR operation satisfies commutative law
XOR operation satisfies the law of association

Topic 1

Title source （ Power button ）： Missing numbers

Title Description ：
Array nums Contains from 0 To n All integers of , But one of them is missing . Please write code to find the missing integer . You have a way O(n) Is it finished in time ？

Example 1：
Input ：[3,0,1]
Output ：2

Example 2：
Input ：[9,6,4,2,3,5,7,0,1]
Output ：8

int missingNumber(int* nums, int numsSize){
    
    int x = 0;
    for(int i = 0; i <= numsSize; i++)
    {
    
        x ^= i;
    }

    for(int i = 0; i < numsSize; i++)
    {
    
        x ^= nums[i];
    }

    return x;
}

Code instructions ：
After the first cycle ,x = 0 ^ 1 ^ 2 ^ 3 ^ … ^ n .
After the second cycle ,x It's the missing number

such as Example 1：
After the first cycle ,x = 0 ^ 1 ^ 2 ^ 3 .
After the second cycle ,x = 0 ^ 1 ^ 2 ^ 3 ^ 3 ^ 0 ^ 1 = 2 .

Topic two

Title source （ Power button ）： The number of occurrences of numbers in an array

Title Description ：
An integer array nums Except for two numbers , The other numbers appear twice . Please write a program to find out these two numbers that only appear once . The required time complexity is O(n), The space complexity is O(1).

Example 1：
Input ：nums = [4,1,4,6]
Output ：[1,6] or [6,1]

Example 2：
Input ：nums = [1,2,10,4,1,4,3,3]
Output ：[2,10] or [10,2]

int* singleNumbers(int* nums, int numsSize, int* returnSize){
    
    int ret = 0;
    for(int i = 0; i < numsSize; i++)
    {
    
        ret ^= nums[i]; 
    }
	 // At the end of the above cycle ,ret  The value of is the result of two numeric XORs that occur only once 
	 // ret  The binary bit of is  1  Bit , That is, two numbers are different in this bit 
	 // such as  ret = 0101 ^ 1001 = 1100 , That is to say, the two bits with different numbers are the number from right to left 3、4 position 
	 
    int m = 1;    // use  m  To find out  ret  The first bit from right to left in the binary bit of is  1  Bit 
    // It won't be an endless cycle , because  ret  Is the result of the XOR of two different numbers , At least one of its binary bits is 1. 
    while((ret & m) == 0)  
    {
     
        m <<= 1;
    }
    // At this time  m  Only one is 1, The position of that one is ret The first number from right to left is 1 Bit 
    // rely on  m  This is 1 The bits of divide the array elements into two groups ： One group is in this position for 0 Of , The other group is in this position for 1 Of .
    // Numbers that appear twice must be grouped into the same group 
    // In other words, the following steps can separate two numbers that only appear once 
    int a = 0, b = 0;
    for(int i = 0; i < numsSize; i++)
    {
    
        if((nums[i] & m) == 0)
            a ^= nums[i];
        else
            b ^= nums[i];
    }
    
    int* retArr = (int*)malloc(sizeof(int)*2);
    retArr[0] = a;
    retArr[1] = b;
    *returnSize = 2;
    return retArr;
}

notes ： Bitwise operators （ & 、^ 、 | ） The priority ratio == and != The priority is lower , Therefore, you want to perform bitwise operation first, and then judge whether to wait or not , You need to put a layer of parentheses around bitwise operations .

If you don't know the nature of XOR , It is hard to think that the solution of the problem is related to XOR , Or I didn't think of it at all . Even if you know the nature of XOR , It's hard to think of it all at once . Only do more questions , Only then has such train of thought .

More articles
Add large numbers （C Language ）
Merge two ordered arrays （C Language ）
Zero after factorial （C Language ）
Adjust the array order so that the odd Numbers precede the even Numbers （C Language ）