Who invented xor

It follows that the result of any sequence of xor operations is completely independent of the order of the operands that is, the order of the elements in the array. In the problem we have an expression where each element Ai appears twice except some singular element B.

Some problems can be solved quickly using bit manipulation. After familiarizing with Boolean operators and their properties, and seeing enough applications like this one, you will naturally "feel" when they're useful to solve a given problem. The key intuitive aspect that distinguishes XOR from the other logical operators is that it is lossless , or non-lossy , meaning that, unlike AND , and OR and more similar to NOT in this regard , it is deterministcally reversible: You can exactly recover one of the input values given the rest of the computation history.

The following diagrams illustrate that AND and OR each have at least one case where the state of one of the inputs is irrecoverable, given a certain value of the other input. I indicate these as "lost" inputs. For the XOR gate, there is no condition in which an input or output value cannot be recovered, given the rest of the computation history. In fact, there's a symmetry that knowing any two values of the triple in0, in1, out allows you to recover the third.

In other words, regardless of input or output, each of these three values is the XOR of the other two! By toggling one of the inputs the upper one in the example above , you can control whether or not the other lower one is negated.

In accordance with its symmetry and information-preserving properties, XOR should come to mind for problems that require reversibility or perfect data recovery. The most obvious example is that XOR ing a dataset with a constant 'key' trivially obscures the data such that knowing the key which might be kept "secret" , allows for exact recovery.

Preserving all of the available information is also desirable in hashing. Because you want hash values that maximally discriminate amongst the source items, you want to make sure that as many of their distinguishing characteristics as possible are incorporated, minimizing loss, in the hash code. Note that in this example, information is lost even though XOR was used. The original value of ul is not recoverable from the hash code, because with that value alone you don't have two out of the three bit values that were used in the internal computation.

Recall from above that you need to retain any two out of the three values for perfect reversal. Out of the resulting hash code and the two values that were XOR ed, you may have saved the result, but typically do not save either of the latter to use as a key value for obtaining the other.

As an amusing aside, XOR was uniquely helpful in the days of bit-twiddling hacks. On a more serious note, the fact that XOR is non-lossy has important information-theoretical implications for futuristic computing, due to an important relationship between information processing and the Second Law of Thermodynamics. Indeed, the notion of entropy plays a central role in quantifying how information "loss" is re- expressed as heat this also being the same prominent relation from Steven Hawking's famous black hole wager.

In this speculative future-generation of CPUs, XOR 's ability to preserve information— and thus shunt away heat —would be invaluable for increasing computational density i.

In this simple example, the relevant 3 values would be the hash code plus the upper- and lower-parts of the original ulong value. Of course the original hashed 'data' itself, represented by ul here, likely is retained. XOR is always defined in terms of binary digits or some equivalent notions, like true or false statements.

Let A and B be two boolean variables, and let XOR be a boolean function that takes two boolean variables. A hint: The question which asks to find one element which has unique property apart from rest, requires bit manipulation. Example: Given an array where every element occurs three times, except one element which occurs only once. Find the element that occurs once. One simple operation that can be done on the array is to choose a property P and count the number of elements of the array that satisfy the property.

For example, if P is the property of being divisible by 5, we can loop through the array and count the number of elements that are divisible by 5. The precondition on the array allows us to gain information about the singleton element from such a count. If the number of elements satisfying P is odd, then the singleton has property P. If the number of elements satisfying P is even, then the singleton must not have property P. For example, if we count 3 elements divisible by 5, then the singleton must have been divisible by 5.

Therefore, if we can invent a collection of properties such that knowing whether each property is true or false will fully specify any element, we can get the answer by counting the number of elements with each property and checking the parity of the counts. There are many different collections of properties that will work. We may as well be efficient, though.

So, we need at least b different properties to fully specify a b -bit number. One such minimal collection of properties that is easy for a computer to test is the collection where the n th property is "Does the number have a 1 in the n th bit?

If we know the answer to this question for each n , then clearly we can reconstruct the number. Another optimization is that we don't have to keep track of the total count of elements satisfying a property; we only need the parity. That is a dot surrounded by circle.

The inverse is XOR! Boolean Algebra is used to analyze and simplify the digital logic circuits. It uses only the binary numbers i. It is also called as Binary Algebra or logical Algebra. Boolean algebra was invented by George Boole in To find XOR of more than two numbers, represent all numbers in binary representation, add 0's before if necessary.

To find each bit of XOR just calculate number of 1's in the corresponding bits. If it is even or zero then that XOR 'ed bit is 0. If it is odd then that XOR 'ed bit is 1. Two of the three inputs will feed one of the 2- input XOR gates.

The output of the first gate will, then, be XORed with the third input to get the final output. An XOR gate sometimes referred to by its extended name, Exclusive OR gate is a digital logic gate with two or more inputs and one output that performs exclusive disjunction. The output of an XOR gate is true only when exactly one of its inputs is true. XOR Gate. Input A Input B Output true true false. A NOR gate is a logic gate which gives a positive output only when both inputs are negative. This is the reason an XOR gate also called anti-coincidence gate or inequality detector.

This gate is called as XOR or exclusive OR gate because, its output is only 1 when one of its input is exclusively 1. X-OR gate is an odd parity checker because it gives high output for odd number of high inputs. So from the above result we can see that, Y will be 1 only when we get. The second line comprises an expression that evaluates to a and stores it in b , just as the toggling example did. The third line comprises an expression that evaluates to b and stores it in a.

This is an example of aliasing , where two arguments to a function share the same location in memory, so altering one will affect the other. Perhaps there is some retribution for this much maligned idea, however.

This is more than just a devious trick when we consider it in the context of assembly language. A node in a singly linked list contains a value and a pointer to the next node. A node in a doubly linked list contains the same, plus a pointer to the previous node. Note that the nodes at either end store the address of their neighbours. Then the code to traverse the list looks like Listing 1, which was adapted from Stackoverflow [ Stackoverflow ].

This uses the same idea as before, that one state is the key to getting at the other. If we know the address of any consecutive pair of nodes, we can derive the address of their neighbours. In particular, by starting from one end we can traverse the list in its entirety. A nice feature of this function is that this same code can be used to traverse either forwards or backwards. XOR can also be used to generate pseudorandom numbers in hardware.

A pseudorandom number generator whether in hardware or software e. This can be achieved very fast in hardware using a linear feedback shift register. To generate the next number in the sequence, XOR the highest 2 bits together and put the result into the lowest bit, shifting all the other bits up by one.

This is a simple algorithm but more complex ones can be constructed using more XOR gates as a function of more than 2 of the lowest bits [ Yikes ]. By choosing the architecture carefully, one can construct it so that it passes through all possible states before returning to the start of the cycle again Figure 4. The essence of encryption is to apply some key to an input message in order to output a new message.

The encryption is only useful if it is very hard to reverse the process. We can achieve this by applying our key over the message using XOR see Listing 2. The choice of key here is crucial to the strength of the encryption. If it is short, then the code could easily be cracked using the centuries-old technique of frequency analysis. As an extreme example, if the key is just 1 byte then all we have is a substitution cipher that consistently maps each letter of the alphabet to another one.

This is known as a stream cipher , and in a real-worl situation this would also be combined with a secure hash function such as md5 or SHA Another type of cipher is the block cipher which operates on the message in blocks of fixed size with an unvarying transformation. The best-known encryption method is the RSA algorithm. Even when the above algorithm is made unbreakable, it has one crucial disadvantage: it is not a public key system like RSA. Using RSA, I can publish the key others need to send me encrypted messages, but keep secret my private key used to decrypt them.

On the other hand, in XOR encryption the same key is used to encrypt and decrypt again we see an example of toggling. Before you can send me encrypted messages I must find a way to secretly tell you the key to use.

If an adversary intercepts that attempt, my code is compromised because they will be able to decrypt all the messages you send me. Now we will see the first application of XOR with respect to parity. There are many ways to defend against data corruption when sending digital information. One of the simplest is to use XOR to combine all the bits together into a single parity bit which gets appended to the end of the message. By comparing the received parity bit with the calculated one, we can reliably determine when a single bit has been corrupted or indeed any odd number of bits.