异或在算法中的应用

二进制运算中,异或无处不在。由于其各种不错的性质在计算机中应用很广。由于日常中很少接触到需要应用到异或的算法,对异或的印象也只停留在各种计算机底层设计中,终归是纸上谈兵。最近接触到了一个使用异或的巧妙算法,便发现自己对异或的理解过于肤浅。 异或简介 交换律 结合律 $x;XOR;0 = x$ | $x;XOR;x = 0$ $A;XOR;\underline{B;XOR;B} = A;XOR;\underline{0} = A $ 使用异或的如上性质,在交换两个变量的值时,可以直接通过异或实现而不用使用额外空间: A = A ^ B; B = B ^ A;//B = B ^ A ^ B = B ^ B ^ A = A A = A ^ B;//A = A ^ B ^ A = B 引子 **问题:**在一个数组中,如果只有一个数重复出现了奇数次而其余数出现了偶数次,设计一个算法来找出这个出现奇数次的数。要求算法满足时间复杂度$O(n)$,空间复杂度$O(1)$。 传统解法 按照传统的思路来的话,可以使用一个HashSet,每次读入一个数据,如果在HashSet中则去掉这个数,反之则将该数字加入HashSet。而这个问题要求$O(1)$的空间复杂度,只能另辟蹊径。 异或解法 可以注意到,这个问题如果使用异或的思想来解决的话便很方便。 假设原数组 nums = {1, 2, 2, 3, 3, 4, 4}所求数字便为 1。初始化Mask = 0,对每个元素都进行运算Mask ^= num[i]。运算后得Mask = 1。即得到了所求的数字。...

April 28, 2020 · Huo Haodong