Differences, or based on binary bit operations, XOR or ^ symbol that the algorithm is the number of operators on both sides of each binary bit, take the same value 0, different values of 1. With Boolean difference is, when the operator on both sides are 1, the Boolean operation result is 1, XOR the result is 0.
Understanding is not simply carry adder, such as 1 +1 = 0,, 0 +0 = 0 +0 = 1.
1, the commutative
2, combined with the law
3, for any number x, there x ^ x = 0, x ^ 0 = x
4, reflexive A XOR B XOR B = A xor 0 = A
XOR is most common in the polynomial division, but it is still the most important properties of reflexivity: A XOR B XOR B = A, that is, given the number of A, the same operation factor (B) for two different or get an A after the operation itself. This is a fantastic character, use of this nature, you can get many interesting applications. For example, all programs will be the textbook for beginners that want to swap two variables, we must introduce an intermediate variable. But if you use XOR, a variable can save storage space: with A, B two variables, the values were stored in a, b, then the following three lines of expression the exchange value of their expression (value) A = A XOR B (a XOR b) B = B XOR A (b XOR a XOR b = a) A = A XOR B (a XOR b XOR a = b) Similarly, the operator can also be used in encryption, data transmission, validation, and so many areas.
The use of distance:
1-1000 with 1001 elements on the array, there is only one element of the value of repetition, the other appears only once. Each array element can only be visited once, to design an algorithm to find it out; do not have secondary storage space, can design an algorithm?
Solution one has apparently been made a more brilliant solution, all the numbers add up, subtract 1 +2 +...+ 1000 and.
This algorithm is perfect enough, I believe the topic and the standard answer is, this algorithm, the only question is, if the series is too large, may result in overflow.
Solution two, different, or do not have this problem, and better performance.
The number of all different or all of the results obtained with 1 ^ 2 ^ 3 ^...^ 1000 the results of XOR, the result is the number of repeats.
However, although this algorithm is very simple, but that it is not an easy thing. XOR this with several features of a relationship.
First XOR meet commutative, associative.
Therefore, 1 ^ 2 ^...^ n ^...^ n ^...^ 1000, no matter in what position two n, can be converted into 1 ^ 2 ^...^ 1000 ^ (n ^ n) form.
Secondly, for any number x, there x ^ x = 0, x ^ 0 = x.
Therefore, 1 ^ 2 ^...^ n ^...^ n ^...^ 1000 = 1 ^ 2 ^...^ 1000 ^ (n ^ n) = 1 ^ 2 ^...^ 1000 ^ 0 = 1 ^ 2 ^...^ 1000 (that is, in addition to the sequence of all n the number of XOR).
Order, 1 ^ 2 ^...^ 1000 (the sequence contains n) the results of T
Then 1 ^ 2 ^...^ 1000 (the sequence contains n) The result is T ^ n.
T ^ (T ^ n) = n.
Therefore, the number of all different or all of the results obtained with 1 ^ 2 ^ 3 ^...^ 1000 the results of XOR, the result is the number of repeats.
Of course, some would say, 1 +2 +...+ 1000 results Gauss's law can be calculated quickly, but in fact a ^ 2 ^...^ 1000 results will also be regular, the algorithm is also more than the law of the Gauss simpler.
Another XOR for encryption is actually very simple, such as C = P ^ K where P is the plaintext, K is the key, C is the ciphertext, recovery can be reflexive P = C ^ K to (make the file signature cover useful).