异或的性质是不一样则为1,那放在本题中该怎么理解呢?这个问题在理解上的难处是异或是一个二元运算,可是解析中没有明确说明谁跟谁进行异或这让我很头疼。
我的理解是因为相同的数值会在异或的过程中互相抵消最后剩下的就是那个惟一的元素,当然这是针对只有一个元素是惟一的而其他的都是成对出现的那种。
那现在数组中惟一的元素不止一个,作者就想能不能把数组拆成两个子数组,其中每个子数组都仅包含一个惟一的元素。
所以他说的这个异或的过程是第一个元素异或第二个元素,其结果再去异或第三个元素,以此类推。
那么关键是怎么进行分组。因为这两个惟一的元素肯定不同,它们异或的结果肯定不为0,从而至少有一位是1,。作者挑选出从左到右第一个1的位置。以数组中元素这一位是不是1为标准分成两组。那问题来了,为什么这样分,那两个惟一的元素不会分到同一组中呢?那是因为数组中元素的异或结果最终是这两个唯一元素的异或结果,而它们那一位之所以为1是由于它们的那一位不同,这是异或的运算性质决定的,所以它俩肯定不会被分配到同一组中去。
那就OK了,此面试题解决了。