异或操作直觉

Question

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

给定一个整数数组,除了一个元素外,每个元素都会出现两次.找一个单一的.

注意:您的算法应具有线性运行时复杂性.你能不用额外的内存来实现吗？

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

首先,为了弄清楚我应该对这个问题使用XOR操作,我应该注意哪些类型的关键字？

另外,为什么向量中的所有项目相互异或,给我们一个不重复的项目？

---

谢谢大家对这些回复,以下是其他任何感兴趣的有关按位属性的更多信息:更多按位信息

Answer 1

1. A ^ 0 == A

2. A ^ A == 0

3. A ^ B == B ^ A

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

(3)和(4)一起表示编号的顺序xor无关紧要.

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

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

因为(1)等于X.

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

Answer 2

Xor运算符是可交换的:

1.      X ? Y = Y ? X                    for any integers X and Y

和关联:

2.      X ? (Y ? Z) = (X ? Y) ? Z      for any integers X, Y and Z

因此,任何xor操作序列的结果完全独立于操作数的顺序(即,数组中元素的顺序).

3.     X ? X = 0                         for any integer X

4.     X ? 0 = 0 ? X = X                for any integer X

在这个问题中我们有一个表达式,其中每个元素Ai出现两次,除了一些奇异元素B.结果Xor操作相当于:

     (A1 ? A1) ? (A2 ? A2) ?    ...   ? B
 = 
         0      ?      0     ?    ...   ? B
 = 
         B

我应该注意哪些类型的关键字,以便弄清楚我应该对这个问题使用XOR操作

使用位操作可以快速解决一些问题.熟悉布尔运算符及其属性,并看到类似这样的应用程序后,您自然会"感觉"它们何时对解决给定问题有用.

Answer 3

区分的关键直观的方面XOR从其他逻辑操作是,它是无损的,或无损的,这意味着,不像AND和OR(更类似于不要在这方面),它是deterministcally可逆的:您可以准确在给定剩余的计算历史记录的情况下恢复其中一个输入值.

下图说明了AND和OR各自至少有一种情况,其中一个输入的状态是不可恢复的,给定另一个输入的某个值.我将这些指示为"丢失"输入.

对于XOR门,在给定剩余的计算历史的情况下,不存在无法恢复输入或输出值的条件.事实上,有一种对称性,知道三重的任何两个值都(in0, in1, out)可以让你恢复第三个.换句话说,无论输入还是输出,这三个值中的每一个都是另外两个的XOR!

这张照片表明,另一种考虑XOR操作的方法是作为可控的非门.通过切换其中一个输入(上例中的上一个输入),您可以控制是否其他(较低)输入被否定.

另一个等效视图是XOR相对于其两个输入实现了正逻辑 非等于(≠)函数.因此在负逻辑下也是等于函数(=).

根据其对称性和信息保持特性,XOR应该考虑到需要可逆性或完美数据恢复的问题.最明显的例子是,对具有常量"密钥"的数据集进行异或操作会使数据变得模糊不清,因此知道密钥(可能保持"秘密")可以实现精确恢复.

在散列中也需要保留所有可用信息.因为您希望哈希值最大程度地区分源项目,所以您希望确保尽可能多地将其区分特征合并到哈希码中,从而最大限度地减少损失.例如,要将64位值散列为32位,您可以使用编程语言XOR运算符,^因为这是一种简单的方法来保证64个输入位中的每一个都有机会影响输出:

uint GetHashCode(ulong ul)
{
    return (uint)ul ^ (uint)(ul >> 32); 
}

请注意,在此示例中,即使使用XOR,信息也会丢失.(事实上​​,'战略信息丢失'是散列的重点).原始值ul不能从哈希代码中恢复,因为仅使用该值,您在内部计算中使用的三个32位值中没有两个.回想一下,您需要保留三个值中的任意两个以实现完美的反转.在生成的哈希代码和XOR ed 的两个值之外,您可能已保存结果,但通常不保存后者中的任何一个以用作获取另一个的键值.¹

作为一个有趣的消息,XOR在那些令人讨厌的黑客攻击时期是独一无二的.我当时的贡献是一种在C/C++中无条件地设置或清除位的方法:

unsigned int v;       // the value to modify
unsigned int m;       // mask: the bits to set or clear
int f;                // condition: 0 to 'set', or 1 to 'clear'

v ^= (-f ^ v) & m;    // if (f) v |= m; else v &= ~m;

更严重的是,由于信息处理与热力学第二定律之间的重要关系,XOR是无损的这一事实对于未来计算具有重要的信息 - 理论意义.正如Charles Seife 解码宇宙的一本优秀且易于理解的书所解释的那样,计算过程中信息的丢失与处理系统发出的黑体辐射有着精确的数学关系.实际上,熵的概念在量化信息"损失"如何(重新)表示为热量方面起着核心作用(这也与史蒂文霍金着名的黑洞赌注具有相同的显着关系).

关于XOR的这种谈话不一定是一个延伸; Seife指出,现代CPU开发目前面临瓦特/cm²半导体材料的基本容限限制,并且解决方案是设计可逆或无损计算系统.在这种推测性的未来一代CPU中,尽管存在这样的材料限制,但XOR保存信息并因此分流热量的能力对于增加计算密度(即MIPS /每平方厘米)是非常宝贵的.

^{1.在这个简单的例子中,相关的3个值将是哈希码加上原始ulong值的上部和下部.当然,由ul此处表示的原始散列"数据"本身可能会被保留.}