由冒泡排序交换数值引发的位操作

翻看B站的视频 讲解算法 说到了冒泡排序中数值交换 发现了一些新的点

两个数字交换的操作， 比如交换数字 a 和 b 的数值：

int c = a;
a = b;
b = a;

以上三行代码，完成数值的交换。

但是， 如果不允许使用新的内存，则可有如下方案：

a = a^b;
b = a^b;
a = a^b;
以上三行代码， 完成数值交换

注意的点

进行交换的两个数值 不在内存的同一个区域。

^操作 可以认为是无进位的加操作

拓展1

一个数组中，只存在一个出现奇数次的数字，其余数字均出现偶数次，找出该数字。

解决方案一

构建一个map，遍历数组， key存储数字，value存储出现的次数，遍历完成后统计map中出现奇数次的key即可。

解决方案二

初始化一个整数0，遍历数组，与该数字进行与或操作，遍历结束，即可得到该奇数数字。

拓展2

一个数组中，存在两个出现奇数次的数字，其余均为偶数次，找出这两个数字。

方案一

类似与拓展1中的方案一，可以获取结果

方案二

初始化数字res = 0，全数组遍历，假设两个不通的数字为a 和 b , 则最终结果为 res = a^b, 因为a b 不相同，所以他们必定在 整数的32位上有不通的一位，所以必定存在一个位为一， 找出这一位，然后按照该位为1进行数组遍历，假设此次数组遍历与或 res1， 则最终得到一个数字为res1 为 a b中一个数字，同时可以res ^ res1 得到另外一个数字。

其中提取出res最右边位置为1 的操作为

int rightFistOne = res &(~res +1);

遍历数组中