Exclusive Or algorithm
- a ^ b = b ^ a
- a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c;
- c= a ^ b Can deduce a = b ^ c. (Commonly used for encryption)
- a ^a = 0.
- a^0 = a.
XOR operation
1. XOR is a mathematical operator. Applied to logical operations.
: The result of true and false is true, the result of false and false is true is also true, the result of true and true is false, and the result of false and false is false. That is to say, the result of the difference between the two values is true.
The method of the exclusive OR operation is a binary operation:
1^1=0
0^0=0
1^0=1
0^1=1
The two are equal to 0 and the other is not equal to 1.
Common related algorithm problems:
1. There are 2n+1 numbers, only one single one, and the others are paired. Find the number of this single one. For example: 2 1 3 2 1.
answer:
XOR calculation, one trip to complete. The time complexity o(n), the answer is 3, because the two identical numbers are XOR 0.
2. 1-1000 are placed in an array containing 1001 elements, only one element value is repeated, and the others only appear once. Each array element can only be accessed once, design an algorithm to find it; without auxiliary storage space, can an algorithm be designed to implement it?
answer:
Let the result of 1^2^…^1000 (not containing n in the sequence) be T
Then the result of 1^2^…^1000 (the sequence contains n) is T^n.
T^(T^n)=n。
Therefore, if all numbers are exclusive ORed, the result obtained is XORed with the result of 1^2^3^...^1000, and the result obtained is a repeated number.
Reference link:/hejun_haitao/article/details/52857474