What does bitwise XOR (exclusive OR) mean?

user_177883 0
Viewed 94965

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?

xor bit-manipulation math language-agnostic operators
8 Answers

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
user_78713260

As it is obvious from the name(bitwise), it operates between bits. Let's see how it works, for example, we have two numbers a=3 and b=4, the binary representation of 3 is 011 and of 4 is 100, so basically xor of the same bits is 0 and for opposite bits, it is 1. In the given example 3^4, where "^" is a xor symbol, will give us 111 whose decimal value will be 7. for another example, if you've given an array in which every element occurs twice except one element & you've to find that element. How can you do that? simple xor of the same numbers will always be 0 and the number which occur exactly once will be your output. because the output of any one number with 0 will be the same name number because the number will have set bits which zero don't have.

user_73343000
Related