The nature and computing XOR

2011-07-10  来源:本站原创  分类:Industry  人气:48 

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.

Nature

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).

相关文章
  • The nature and computing XOR 2011-07-10

    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 side

  • Every beginner should get to know the issues 2010-03-06

    Java Essentials accumulation For this series of questions in each school who should get to know Java. Of course, if only learn Java play on do not care. If you think you have beyond the beginner, but do not really understand these issues, please retu

  • Fermat's little theorem Montgomery algorithm for determining prime numbers 2010-05-25

    x% y to x modulo y, ie x divided by y from the remainder, when x <y the time, x% y = x, all the operands modulo an integer. that x, x ^ y y-th power. Involution operator precedence than multiplication and division, and modulus, addition and subtracti

  • Fermat's little theorem Prime Theorem Montgomery Algorithm 2010-05-25

    x% y to x modulo y, ie x divided by y from the remainder, when x <y the time, x% y = x, all the operands modulo an integer. that x, x ^ y y-th power. Involution operator precedence than multiplication and division, and modulus, addition and subtracti

  • Reveal the "cloud computing infrastructure," the true nature 2010-11-03

    Cloud computing is the most popular of the recent IT technology, is also considered the future of the Internet as well as IT industry trends, industry scale is expected to reach billions of dollars. Now all the technical analysts, magazines, manufact

  • = OO + distributed computing software architecture direction 2009-04-22

    Recently, a new term "cloud computing (cloud computing)" very popular, it is the further refinement of grid computing, we take a look at some of the network on the definition of cloud computing: Google search engine used to calculate more suitab

  • C language bitwise operators: and. Or. XOR. Negated. Left and right shift 2010-07-07

    Language bitwise operators: AND, OR, XOR, take anti, left and right shift Bit operation is carried out according to the binary operation. Software in the system, often need to address the issue of bits. C language provides a six-man operator. These o

  • Into the cloud computing era: the whole cloud computing security analysis 2010-07-07

    Cloud computing as a new term, it is not even figure out the exact definition of cloud computing security question, then, the discussion on cloud computing security is also often found in the media and academic press. However, according to the author

  • Business concern: Analysis of the Ten misconceptions cloud computing 2010-07-08

    Cloud computing is not a grid computing is not virtual, but a variety of products and services integrate end to end solution. Cloud computing is SaaS? Cloud computing is only applicable to SMEs? Cloud computing can not guarantee the security of enter

  • Opened a "cloud computing infrastructure," the essence of true colors (1) 2010-07-10

    Abstract: Cloud computing is recently the most popular IT technologies, is also considered the future of the Internet as well as IT industry trends, industry size is expected to reach 100 billion U.S. dollars. Now that all the technical analysts, mag

  • In-depth understanding of bitwise XOR operator 2010-08-21

    Involved in computing the two values, the same as if the two corresponding bit position, the result is 0, otherwise 1. Namely: 0 ^ 0 = 0, 1 ^ 0 = 1, 0 ^ 1 = 1, 1 ^ 1 = 0 For example: 10100001 ^ 00010001 = 10110000 Bitwise XOR of the three characteris

  • You can call it cloud computing, but do not really think it is a power station 2010-09-15

    Since the concept of cloud computing google made, and its a landmark paper MapReduce Simplified Data Processing on Large Clusters published, a night full of cloud computing to every corner of the whole network, more and more enterprises are rushing t

  • [Java] bitwise XOR operator, a little mind (to) 2010-10-23

    Bitwise exclusive or operator of two operands, if the two corresponding bits are the same, the result is 0, 1 otherwise Namely: 0 ^ 0 = 0, 1 ^ 0 = 1, 0 ^ 1 = 1, 1 ^ 1 = 0 For example: 00101010 ^ 00010111 = 00111101 1) If you need to use a certain int

  • With Linux and Apache Hadoop for cloud computing 2010-10-31

    Original http://www.ibm.com/developerworks/cn/aix/library/au-cloud_apache/ About cloud computing Cloud computing has recently become increasingly popular, and cloud computing has been seen as a new trend in IT industry. Cloud computing can be loosely

  • Lifting of the "cloud computing infrastructure," the essence of true 2010-11-03

    Cloud computing is the most popular recent IT technology, is also considered the future of the Internet as well as IT industry trends, industry scale is expected to reach billions of dollars. Now all the technical analysts, magazines, manufacturers a

  • Analysis of cloud computing technology and industry 2010-11-06

    Original http://www.jsfyun.com/news/world/2010-09-30/90.html IPCC Peng of China Cloud computing Note: (more than two years to our understanding of cloud computing has also been a lot of twists and turns, from the first book, "Approaching cloud comput

  • Bitwise and. Bitwise XOR. To bit 2011-05-04

    & Bitwise and | Bitwise or ^ Bitwise XOR 1. By bit by bit with the operation and operator "&" is a binary operator. Its function is to participate in the operation of the two numbers and the corresponding binary. Only two corresponding b

  • Turn: to promote the standardization of the top ten organizations cloud computing 2011-08-18

    Cloud Ten promote standardization organization Cloud Ten promote standardization organization 2011-8-12 I want to comment on share: Digg This blog references Large | Medium | Small REVIEW: This article discusses the standardization of the basic needs

  • Cloud computing business model need to find a new "landing point" 2011-08-23

    Through analysis and observation, we found that the current cloud computing are mostly personal computing business model for enterprise computing, we can see is the data center (IaaS / IDC), which is based on a business model of IT resources. However

  • Data-intensive computing: MapReduce and Hadoop's really competitive 2011-09-09

    The rapid increase in Internet users and broadband networks, making the nature of Internet services based on massive data processing services for the center. From the search engines, video sharing to e-commerce, Internet services, the success is larg