What does bitwise XOR (exclusive OR) mean?

Question

I'm trying to understand the binary operators in C# or in general, in particular ^ - exclusive or.

For example:

Given an array of positive integers. All numbers occur even number of times except one number which occurs odd number of times. Find the number in O(n) time and constant space.

This can be done with ^ as follows: Do bitwise XOR of all the elements. Finally we get the number which has odd occurrences.

How does it work?

When I do:

int res = 2 ^ 3;  
res = 1;  
int res = 2 ^ 5;  
res = 7;  
int res = 2 ^ 10;  
res = 8;  

What's actually happening? What are the other bit magics? Any reference I can look up and learn more about them?

Solution 1

To see how it works, first you need to write both operands in binary, because bitwise operations work on individual bits.

Then you can apply the truth table for your particular operator. It acts on each pair of bits having the same position in the two operands (the same place value). So the leftmost bit (MSB) of A is combined with the MSB of B to produce the MSB of the result.

Example: 2^10:

    0010 2
XOR 1010 8 + 2
    ----
    1    xor(0, 1)
     0   xor(0, 0)
      0  xor(1, 1)
       0 xor(0, 0)
    ----
 =  1000 8

And the result is 8.

Solution 2

I know this is a rather old post but I wanted simplify the answer since I stumbled upon it while looking for something else.
XOR (eXclusive OR/either or), can be translated simply as toggle on/off.
Which will either exclude (if exists) or include (if nonexistent) the specified bits.

Using 4 bits (1111) we get 16 possible results from 0-15:

 decimal | binary | bits (expanded)
       0 | 0000   | 0
       1 | 0001   | 1
       2 | 0010   | 2
       3 | 0011   | (1+2)
       4 | 0100   | 4
       5 | 0101   | (1+4)
       6 | 0110   | (2+4) 
       7 | 0111   | (1+2+4)
       8 | 1000   | 8
       9 | 1001   | (1+8)
      10 | 1010   | (2+8)
      11 | 1011   | (1+2+8)
      12 | 1100   | (4+8)
      13 | 1101   | (1+4+8)
      14 | 1110   | (2+4+8)
      15 | 1111   | (1+2+4+8)

The decimal value to the left of the binary value, is the numeric value used in XOR and other bitwise operations, that represents the total value of associated bits. See Computer Number Format and Binary Number - Decimal for more details.

For example: 0011 are bits 1 and 2 as on, leaving bits 4 and 8 as off. Which is represented as the decimal value of 3 to signify the bits that are on, and displayed in an expanded form as 1+2.

---

As for what's going on with the logic behind XOR here are some examples
From the original post

2^3 = 1

• 2 is a member of 1+2 (3) remove 2 = 1

2^5 = 7

• 2 is not a member of 1+4 (5) add 2 = 1+2+4 (7)

2^10 = 8

• 2 is a member of 2+8 (10) remove 2 = 8

---

Further examples

1^3 = 2

• 1 is a member of 1+2 (3) remove 1 = 2

4^5 = 1

• 4 is a member of 1+4 (5) remove 4 = 1

4^4 = 0

• 4 is a member of itself remove 4 = 0

1^2^3 = 0
Logic: ((1^2)^(1+2))

• (1^2) 1 is not a member of 2 add 2 = 1+2 (3)
• (3^3) 1 and 2 are members of 1+2 (3) remove 1+2 (3) = 0

1^1^0^1 = 1
Logic: (((1^1)^0)^1)

• (1^1) 1 is a member of 1 remove 1 = 0
• (0^0) 0 is a member of 0 remove 0 = 0
• (0^1) 0 is not a member of 1 add 1 = 1

1^8^4 = 13
Logic: ((1^8)^4)

• (1^8) 1 is not a member of 8 add 1 = 1+8 (9)
• (9^4) 1 and 8 are not members of 4 add 1+8 = 1+4+8 (13)

4^13^10 = 3
Logic: ((4^(1+4+8))^(2+8))

• (4^13) 4 is a member of 1+4+8 (13) remove 4 = 1+8 (9)
• (9^10) 8 is a member of 2+8 (10) remove 8 = 2

• 1 is not a member of 2+8 (10) add 1 = 1+2 (3)

4^10^13 = 3
Logic: ((4^(2+8))^(1+4+8))

• (4^10) 4 is not a member of 2+8 (10) add 4 = 2+4+8 (14)
• (14^13) 4 and 8 are members of 1+4+8 (13) remove 4+8 = 1

• 2 is not a member of 1+4+8 (13) add 2 = 1+2 (3)

Solution 3

The other way to show this is to use the algebra of XOR; you do not need to know anything about individual bits.

For any numbers x, y, z:

XOR is commutative: x ^ y == y ^ x

XOR is associative: x ^ (y ^ z) == (x ^ y) ^ z

The identity is 0: x ^ 0 == x

Every element is its own inverse: x ^ x == 0

Given this, it is easy to prove the result stated. Consider a sequence:

a ^ b ^ c ^ d ...

Since XOR is commutative and associative, the order does not matter. So sort the elements.

Now any adjacent identical elements x ^ x can be replaced with 0 (self-inverse property). And any 0 can be removed (because it is the identity).

Repeat as long as possible. Any number that appears an even number of times has an integral number of pairs, so they all become 0 and disappear.

Eventually you are left with just one element, which is the one appearing an odd number of times. Every time it appears twice, those two disappear. Eventually you are left with one occurrence.

[update]

Note that this proof only requires certain assumptions about the operation. Specifically, suppose a set S with an operator . has the following properties:

Assocativity: x . (y . z) = (x . y) . z for any x, y, and z in S.

Identity: There exists a single element e such that e . x = x . e = x for all x in S.

Closure: For any x and y in S, x . y is also in S.

Self-inverse: For any x in S, x . x = e

As it turns out, we need not assume commutativity; we can prove it:

(x . y) . (x . y) = e  (by self-inverse)
x . (y . x) . y = e (by associativity)
x . x . (y . x) . y . y = x . e . y  (multiply both sides by x on the left and y on the right)
y . x = x . y  (because x . x = y . y = e and the e's go away)

Now, I said that "you do not need to know anything about individual bits". I was thinking that any group satisfying these properties would be enough, and that such a group need not necessarily be isomorphic to the integers under XOR.

But @Steve Jessup proved me wrong in the comments. If you define scalar multiplication by {0,1} as:

0 * x = 0
1 * x = x

...then this structure satisfies all of the axioms of a vector space over the integers mod 2.

Thus any such structure is isomorphic to a set of vectors of bits under component-wise XOR.

Solution 4

This is based on the simple fact that XOR of a number with itself results Zero.

and XOR of a number with 0 results the number itself.

So, if we have an array = {5,8,12,5,12}.

5 is occurring 2 times. 8 is occurring 1 times. 12 is occurring 2 times.

We have to find the number occurring odd number of times. Clearly, 8 is the number.

We start with res=0 and XOR with all the elements of the array.

int res=0; for(int i:array) res = res ^ i;

    1st Iteration: res = 0^5 = 5
    2nd Iteration: res = 5^8 
    3rd Iteration: res = 5^8^12
    4th Iteration: res = 5^8^12^5 = 0^8^12 = 8^12
    5th Iteration: res = 8^12^12 = 8^0 = 8

Solution 5

The bitwise operators treat the bits inside an integer value as a tiny array of bits. Each of those bits is like a tiny bool value. When you use the bitwise exclusive or operator, one interpretation of what the operator does is:

• for each bit in the first value, toggle the bit if the corresponding bit in the second value is set

The net effect is that a single bit starts out false and if the total number of "toggles" is even, it will still be false at the end. If the total number of "toggles" is odd, it will be true at the end.

Just think "tiny array of boolean values" and it will start to make sense.

View more solutions