def

j后i甲^乙j(甲^乙)^乙甲^(乙^乙)甲^0甲基于性质1和性质2的结合律

经第三句i

在写排序时候我们通常需要做交换操作交换数组中的两个数。

如选择排序中我们需要将子数组中最小的数与当前第一位数字交换又如冒泡排序中我们需要通过两两交换来将最大的数交换到子数组的最高位。

也就是说我们想要交换arr[i]和arr[j]而此时ij时交换会失败因为当指向同一片内存区域时代码就类似于变成了

def

i自身与自身的相与结果为0所以这样的操作会将原本数组中的数抹成0而不是保留原数

若只是交换i、j的值i和j不指向同一片内存区域则可以成功i和j的值相等也不会被抹成0。

听到的一个说法是原理是靠内存地址来异或的。

经典面试题1

arr中有一种数出现了奇数次其他数出现了偶数次请找出这种奇数次的数。

5.2

通过异或解决因为同样的数与自身相异或结果为0偶数条件下也为0异或的性质1而出现奇数次的数与0相与的结果为数的本身。

所以只需要将所有的变量异或上就行了。

5.3

arr中有两种数出现了奇数次其他数出现了偶数次请找出这两种出现了奇数次的数

6.2

通过5中的题目可以知道通过将本题arr中所有数异或得到的结果应该为a_xor_b

a^b

考虑的方向是既然a和b是两个不相等的数那么a^b的结果一定存在1从二进制上考虑a^b的二进制中肯定存在1

那么这个1就可以作为突破的方向假设我们从a^b中找到第2位上的数为1则证明a二进制的第2位和b二进制的第2位是不相等的一个为0另一个为1a可能为0/1b同理

此时arr中的数可以分为两类一类是在第2位上为1的另一类是在第2位上为0的而a和b肯定是分属两类

通过将所有第2位上为1的数进行异或或将所有第2位上为0的数进行异或得到的肯定是a和b的其中一个。

因为a和b分别属于这两个类中出现奇数次的数其他偶数次的在异或过程中已经消为0了。

a^b再与找到的数可能是a也可能是b进行异或得到的就是另外一个。

6.3

arr中有两种数出现了奇数次其他数出现了偶数次请找出这两种出现了奇数次的数if

__name__

a_xor_ba^b既然a和b是两个不同的数a_xor_b中一定存在某一位为1right_one

a_xor_b