Shulou(Shulou.com)06/02 Report--

This article mainly explains "Java XOR". The content in the article is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "Java XOR".

Preface

XOR is a binary-based bit operation, represented by the symbol XOR or ^, whose algorithm is 0 for each binary bit of the number on both sides of the operator, and 1 for the different value.

Nature

1. Exchange law

2. The law of association (i.e. (a ^ b) ^ c = = a ^ (b ^ c))

3. For any number x, there are x ^ x = 0, x ^ 0 = x

4. Reflexive A XOR B XOR B = A XOR 0 = A

XOR operation is most common in polynomial division, but its most important property is reflexivity: A XOR B XOR B = A, that is, for a given number A, An is still obtained after two XOR operations with the same operation factor (B). This is a magical property, and many interesting applications can be obtained by using this property. For example, all program textbooks point out to beginners that in order to exchange the values of two variables, an intermediate variable must be introduced. However, if you use XOR, you can save the storage space of a variable: if there are two variables, and the stored values are aforce b, the following three-line expressions will interchange their value expressions (values):

A XOR B (a XOR b) B XOR A (b XOR a XOR b = a) An A XOR B (a XOR b XOR a = b)

Example:

Int a = 10, b = 5a = a ^ b, b = a ^ b

Similarly, this operation can also be used in many fields, such as encryption, data transmission, parity and so on.

Application example: 1-1000 is placed in an array of 1001 elements, only one element value is repeated, and the others appear only once. Each array element can only be accessed once, design an algorithm to find it; without auxiliary storage space, can you design an algorithm to implement?

Solution 1. It is obvious that someone has come up with a wonderful solution, which adds up all the numbers and subtracts the sum of 1, 2, 2, 000. This algorithm is perfect enough to believe that the standard answer of the author is this algorithm. the only problem is that if the sequence is too large, it may lead to overflow.

Solution 2, XOR does not have this problem, and the performance is better. If all the numbers are XOR, the result is XOR with the result of 1 ^ 2 ^ 3 ^. ^ 1000, and the result is the repeated number.

But although the algorithm is very simple, it is not an easy task to prove. This is related to several features of XOR operations. First of all, the XOR operation satisfies the commutative law and the association law.

Therefore, 1 ^ 2 ^. N ^. N ^ 1000, no matter where these two ns appear, can be converted into the form of 1 ^ 2 ^. ^ 1000 ^ (n ^ n). Second, for any number x, there are x ^ x = 0, x ^ 0 = x.

So 1 ^ 2 ^.. ^ n ^. ^ 1000 = 1 ^ 2 ^. ^ 1000 ^ (n ^ n) = 1 ^ 2 ^. ^ 1000 = 1 ^ 2. ^ 0 = 1 ^ 2. ^ 1000 (that is, the exclusive OR of all numbers except n in the sequence). So that the result of 1 ^ 2 ^. ^ 1000 (n is not included in the sequence) is T.

The result of 1 ^ 2 ^.. ^ 1000 (which contains n in the sequence) is T ^ n.

T ^ (T ^ n) = n.

So, if all the numbers are XOR, the result is XOR with the result of 1 ^ 2 ^ 3 ^. ^ 1000, and the result is the repeated number.

Of course, some people will say that the result of 1 ^ 2 ^. 1000 can be calculated quickly by Gauss law, but in fact, the result of 1 ^ 2 ^ 1000 is regular, and the algorithm is much simpler than Gauss law.

The deformation of google interview questions: an array stores several integers, one number appears odd times, and the other numbers appear even times. Find out the number that appears odd times?

Public void fun () {int a [] = {22,38,38,22 System.out.println 22, 4, 4, 11, 11}; int temp = 0; for (int I = 0; I < a.temperth; iCool +) {temp ^ = a [I];} System.out.println (temp);}

There are many solutions, but the best is the same as above, is to put all the numbers XOR, the final result is to find, the principle is the same as above!

* * split line * *

This can be achieved without introducing the third variable to achieve the exchange, but the calculation is more than the third variable, so it will be less efficient.

About other methods, there are: int axiom 5, Benz10; axiafub; / / axiajie 15, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 5, 5, 5, 5, 6, 6, 6, 6, 6, 4, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,

But there is a drawback. If it runs in a vc6 environment, then the size of the int is 4 Bytes, so the maximum value stored in the int variable is 2 ^ 31-1, that is, 2147483647. If we make the value of a 2147483000pm b 1000000000, then the addition of an and b is out of bounds.

In fact, from the actual operation statistics, we find that there is a high probability that the two variables to be exchanged have the same number, and there are very few cases of subtraction and crossing the boundary between them, so we can exchange the addition and subtraction above. This reduces the probability of program error:

Int axiom 5 recollection baud 10; a-= b; / Alavmai 5 recollection baud 10 b + = a; / / baud 5pas 5a = b-a; / / axiom 10 meme baud 5

Through the above operations, the values in an and b are exchanged. It looks simple on the surface, but it's not easy to think of, especially after getting used to introducing the algorithm of the third variable. Its principle is that an and b are regarded as points on the number axis and calculated around the distance between the two points.

The specific process is as follows: the first sentence, "a murmur b", calculates the distance between the two points of ab and saves it in a; the second sentence, "b", calculates the distance from a to the origin (the difference between the distance from b to the origin and the distance between the two points of ab), and saves it in b; the third sentence, "b", calculates the distance from b to the origin (the sum of the distance from a to the origin and the distance from ab), and saves it in a. Complete the exchange.

Thank you for your reading, the above is the content of "Java XOR what", after the study of this article, I believe you have a deeper understanding of what Java XOR is, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.