# XOR Operation Intuition

The Xor operator is *commutative*:

```
1. X ⊕ Y = Y ⊕ X for any integers X and Y
```

and *associative*:

```
2. X ⊕ (Y ⊕ Z) = (X ⊕ Y) ⊕ Z for any integers X, Y and Z
```

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

```
3. X ⊕ X = 0 for any integer X
4. X ⊕ 0 = 0 ⊕ X = X for any integer X
```

In the problem we have an expression where each element Ai appears twice except some singular element B. the resulting Xor operation is equivalent to:

```
(A1 ⊕ A1) ⊕ (A2 ⊕ A2) ⊕ ... ⊕ B
=
0 ⊕ 0 ⊕ ... ⊕ B
=
B
```

what sorts of keywords should I be paying attention to in order to figure out that I should be using an XOR operation for this question

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.

XOR is always defined in terms of binary digits (or some equivalent notions, like true or false statements). There is no special XOR for integers other than the XORing of corresponding bits of their binary representations.

Let A and B be two boolean variables, and let XOR be a boolean function that takes two boolean variables.

A⊕B = 1 if either (A = 0 and B = 1) or (A = 1 and B = 0) (i.e. they are different),

A⊕B=0 if either (A = 0 and B = 0) or (A = 1 and B = 1). (i.e they are same)

Thus taking your question into consideration since out of given n elements of the vector ,every element appears twice except one element,the idea is that the binary representation of the duplicate numbers would be same thus there XOR result would nullify each other as 1⊕1 =0 and 0⊕0= 0.

For A=5 ,its binary representation is 101,so A⊕A = (101)⊕(101) = 000 which is the decimal representation is 0.

REMEMBER IT DOES NOT MATTER IN WHICH ORDER THE NUMBERS APPEAR AFTER EACH OTHER BECAUSE ((A⊕B)⊕C) = (A⊕(B⊕C)) . Eventually what you get at the end after XORING every number is the number which occurs once .

To answer your question regarding when you need to use XOR operations for solving a question, practice some BIT MANIPULATION question eventually you will be able to figure out.

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 .

`A ^ 0 == A`

`A ^ A == 0`

`A ^ B == B ^ A`

`(A ^ B) ^ C == A ^ (B ^ C)`

(3) and (4) together mean that the order in which numbers are `xor`

ed doesn't matter.

Which means that, for example, `A^B^X^C^B^A^C`

is equal to `A^A ^ B^B ^ C^C ^ X`

.

Because of the (2) that is equal to `0^0^0^X`

.

Because of the (1) that is equal to `X`

.

I don't think there are any specific keywords that can help you to identify such problems. You just should know above properties of XOR.

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 unary-`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!

From the discussion so far, one intuition could be that `xor`

works like a * whack-a-mole*.

On further examination, the picture also suggests that you can think of the `xor`

operation is as a **controllable unary- not** gate. 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.

Yet another equivalent view is that `xor`

implements the positive-logic **not-equals** (≠) function with respect to its two inputs. And thus also the **equals** function (=) under negative-logic.

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. For example, to hash a 64-bit value into 32 bits, you would use the programming language `xor`

operator `^`

because it's an easy way to guarantee that each of the 64 input bits has an opportunity to influence the output:

```
uint GetHashCode(ulong ul)
{
return (uint)ul ^ (uint)(ul >> 32);
}
```

Note that in this example, information is lost even though `xor`

was used. (In fact, "strategic information loss" is kind-of a definition of hashing). 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 32-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 ("whack-a-mole"). 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.^{1}

As an aside,

`xor`

was helpful in the days of bit-twiddling hacks. My contribution back then was a way toconditionally set or clear bit(s) without branchingin C/C++:`unsigned int v; // input, output: the value to modify unsigned int m; // mask: which bit(s) to set or clear int f; // action: 0 to 'set', or 1 to 'clear' them v ^= (-f ^ v) & m; // if (f) v |= m; else v &= ~m;`

Finally, 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. As explained in an excellent and accessible book by Charles Seife, *Decoding the Universe*, it turns out that the loss of information during computation has an exact physical correspondence with the black-body radiation emanated by a processing system, a limit known as Landauer's principle.

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

Such talk regarding `xor`

is not necessarily academic; Seife notes that modern CPU development currently faces fundamental toleration limitations on the **watts/cm²** of semiconducting materials, and that a solution would be to design reversible, or lossless, computing systems. 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.e., MIPS/per cm²) despite such materials limitations.

^{1. 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.}