Farenew的博客

2019.07.24

1. 异或

XOR操作是一个非常有用的操作, XOR操作下对布尔值的集合是可以构成一个群的. 在计算机科学中有着广泛的应用. 对于解题的时候, 我目前发现了有这么几种用处:

  • 1. 两个不同的元素XOR操作不等于0, 两个相同的元素XOR操作等于0.
  • 2. 不同的集合取XOR值是不同的.

1.1 XOR元素操作

针对这个题, 有一个非常好的leetcode的题:

leetcode 136

Given a non-empty 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?

Example 1:

Input: [2,2,1]
Output: 1

Example 2:

Input: [4,1,2,1,2]
Output: 4

解答

使用异或, 一个数和另一个数的异或, 如果两个数字相等, 结果为0, 否则不为0.

int singleNumber(vector<int>& nums) {
    int out = nums[0];
    for(int i=1; i<nums.size(); i++)
        out ^= nums[i];
    
    return out;
}

1.2 XOR集合操作

对一个集合取XOR值, 也是一个常用的编码方式, 即常用的异或校验. 但是使用异或校验并不能用来作为一个集合的hash值. 这是因为不同的元素可能产生相同的异或值.

2. 使用位运算来遍历元素

对于一个集合来讲, {a,b,c}, 完全可以使用3个bit来表示. 每个bit表示取或者不取. 这就是使用位运算来实现组合了. 对于{a,b,c}的不同元素的取和不取, 刚好构成了{a,b,c}的幂集. 这个循环就是从000111的一个遍历.

这部分内容的实现以及进一步地取对应个数的方法, 我在github上放过相关内容, 请参考: 通过位运算实现基础的遍历