异或操作直觉 [英] XOR Operation Intuition

问题描述

我最近在Leetcode上遇到了这个问题，并想出了一个需要澄清的解决方案:

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;
    }
};

首先，为了弄清楚我应该对这个问题使用XOR操作，我应该注意哪些关键词?

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

推荐答案

1. A ^ 0 == A

A ^ A == 0

A ^ B == B ^ A

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

(3)和(4)一起意味着xor编号的顺序无关紧要.

(3) and (4) together mean that the order in which numbers are xored doesn't matter.

例如，这意味着A^B^X^C^B^A^C等于A^A ^ B^B ^ C^C ^ X.

因为(2)等于0^0^0^X.

因为(1)等于X.

我认为没有任何特定的关键字可以帮助您识别此类问题.您只应该了解XOR的上述属性.

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.

这篇关于异或操作直觉的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！