XOR operation and its usage

Exclusive or operator ∧, Same as 0, Different for 1

nature ：

①0∧N=N, N∧N=0

② Satisfying the commutative law , Associative law

namely a∧b=b∧a,(a∧b)∧c=a∧(b∧c)

③ Do XOR operation on the same batch of numbers , The result of the operation is independent of the operation order

XOR operation can be understood as Carry free addition , for example 10110∧00111=10001

---

application ：

One 、 XOR operation realizes the exchange of two numbers ：

a=a∧b;

b=a∧b;

a=a∧b;

explain ： At the beginning a= nail ,b= B ;

After the first line runs ：a= nail ∧ B ,b= B ;

After the second line runs ：a= nail ∧ B ,b= nail ∧（ B ∧ B ）= nail ∧0= nail ;

After the third line runs ：a= nail ∧ B ∧ nail =（ nail ∧ nail ）∧ B =0∧ B = B

Realize exchange . But pay attention ： Only two different numbers can be used

Two 、 subject ：① In an integer array , Only one number appears odd times , The other numbers appear even times , Find out the number that occurs an odd number of times ;② It is known that two groups of numbers appear an odd number of times , All other numbers appear even number of times. Find these two numbers .

Explain ：① Define a variable eor=0, In turn eor XOR with each number in the array , The final result is the number of odd occurrences （ The XOR between numbers that appear even times is equal to 0, And the odd number of times will leave one , Any number and 0 XOR is equal to itself , Therefore, the number of odd times remains ）

② Suppose the number of the two odd occurrences to be found is a,b. Use the same idea , Let variables eor=0 Do exclusive or operations with all numbers in the array , The result eor=a^b, And know eor=a^b≠0, therefore eor Someone must be 1, namely a And b Different in this one . that , We assume that eor by 1 This one of is the No x position （x It is known. ）, Redefining variables eor'=0, And combine it with all the numbers in the array x It's not 1 Number of numbers , Final eor' obtain a or b. Last eor^eor' Get another number .

  Code No. 24 Explain ：

hypothesis eor=100010, Take the opposite ~eor=011101, Again +1 have to 011110,eor&（~eor+1）=000010 Or get eor The rightmost of the 1