math - 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?

Answer 1

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)