Search code examples
c++algorithmbit-manipulationxor

XOR Operation Intuition

I recently came across this question on Leetcode and figured out a solution that I need some clarification with:

Given an array of integers, every element appears twice except for one. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = 0;
        for(auto & c : nums) {
            result ^= c;
        }
        return result;
    }
};

First of all, 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?

Also, why does XOR'ing all items in the vector with each other give us the one that is not repeated?

Thank you all for these responses, here is some more information on bitwise properties for anyone else interested: More bitwise info

Solution

    1. A ^ 0 == A

    2. A ^ A == 0

    3. A ^ B == B ^ A

    4. (A ^ B) ^ C == A ^ (B ^ C)

    (3) and (4) together mean that the order in which numbers are xored 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.