Leetcode question 136 [single number]

Subject requirements

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.

analysis

The title stem says that all integer elements in a non empty array appear in pairs , Only one element appears once , Find this element .
in addition , The topic also requires that the complexity should be linear , In this case, simple loop nesting will not work , Because the complexity of nested loops is nonlinear .
When looking up data , Found a more ingenious method , Record here . This method makes use of the property of XOR operation in computer bit operation .

0^0=0
1^0=1
1^1=0
0^1=1

• 0 Exclusive or 0 by 0
• 0 XOR any number for itself
• 1 XOR any number negates it
• Any number XOR is itself 0

a ^ 0 = a
a ^ a = 0 

Same as 0, Different for 1.
Besides , XOR operation also follows commutative law and associative law . namely

a^b^c^a^b
=(a^a)^(b^b)^c
=0^0^c
=c

Based on the above rules , The train of thought of this question is also there . XOR all the elements in the array , The last value is the element value that appears only once .

c Language implementation

#include <stdio.h>
int singleNumber(int* nums, int numsSize){
    
    int i=0;
    int t=0;
    for (i=0;i<numsSize;i++){
    
        t = nums[i]^t;
    }
    return t;
}
int main(){
    
    int arr[9] = {
    6,5,11,4,3,3,4,5,6};
    int t;
    t = singleNumber(arr, 9);
    printf("%d\n",t);
}