Java千问：Java位运算经典应用(二)

接上篇

三、不借助中间变量交换两个变量的值

通常情况下，我们要交换两个变量的值都按如下步骤操作：

这种操作方式不难理解，实现交换变量值的关键点就在于中间变量c。而现在的题目要求是不借助中间变量来交换a和b的值。如果不使用位运算的方式，同样可以做到不借助中间变量交换两个变量的值，其实现过程如下。

为了讲解方便，我们把最初a与b的值称之为原始a和原始b，3行代码就是3步操作：

第1步：把原始a与原始b相加的和存储到变量a中，变量b的值暂时没有发生变化。

第2步：用这个和减去原始b，再赋值到变量b中，经过这一步运算，变量b中就保存了原始a的值。

第3步：用原始a、b之和减去原始a的值，就得到原始b，并且把这个值保存到变量a中。

通过以上3步就实现了a、b两个变量在不借助中间变量的情况下进行值的交换。这种算法虽然没有借助中间变量，但有一个问题是如果a和b都是较大的数，在做第1步操作的时候就有可能出现两值相加的和超出int类型的最大值，产生溢出的现象，从而导致后面的运算全部出错。

而我们用位运算的方式实现交换，就不存在这个问题了。具体代码如下：

讲述这段代码之前，先回顾一个运算规律，那就是：a^b^b的运算结果等于a。对此运算规律有疑义，请阅读《Java千问：Java语言位运算符详解》一文。为了表述方便，我们把a^b的操作称之为”用b对a加密”，之所以这么称呼，就是因为a与b进行了异或运算之后，得到一个全新的值，效果如同对a加密一样。而把a^b^b的操作称之为”还原”， 之所以这么称呼，就是因为a^b^b的运算结果等于a，如同是把a的值”加密”之后，又进行了还原，恢复了a的值。

我们还是把a和b最初的值称为原始a和原始b。这三行代码是如何实现变量值交换的呢？我们逐行讲解：

第1行代码：对a用b进行了加密操作，并且又赋值给了变量a，此时变量a就由原始数据变成了加密后的值。

第2行代码：把加密后的值与原始b进行异或运算，就还原了原始a的值，我们把这个值赋值给b，这样变量b中就存储了原始a的值。

第3行代码：用加密后的值与现在的b，也就是保存了原始a的变量进行异或操作，就能得到原始b的值，之后再把原始b的值赋值给变量a，这样就完成了变量a与b值的交换。

    四、找出单身狗元素

    所谓找出单身狗元素就是指：一个数组中，某个数只出现了一次，而其他数都出现了两次，要求编写程序把那个只出现了一次的数找出来。完成这个题目的最核心原理就是: 两个相同的数字进行异或运算，结果为0，而任何一个整数与0进行异或运算，其结果都是这个数本身。另外，任意N个整数进行异或操作，满足交换律。

    按照这个思路，我们只需要把数组中所有的元素都做一遍异或操作，所得到的值就是那个只出现了一次的数字。因为出现了两次的数字，它们之间进行异或操作会变为0。即使这两个数字没有挨在一起，但根据异或运算的交换律我们可以知道：位置关系并不影响运算结果，所以两个相同的数字只要都参与了异或运算，最终的结果都是0。而那个只出现了一次的数字，与0进行异或操作，其结果仍然是它自身的值。因此，异或运算的结果就是那个只出现了一次的数字，我们根据异或运算的结果，就能找出”单身狗”元素了。具体实现代码如下：

这道题目还有另一个版本，题目描述为：有整型数组a和b，a数组中所有元素都出现在b数组中，但b数组比a数组多出一个元素，编写程序找到b数组中多出来的这个元素。虽然变成了两个数组，但实现算法的思路并没有发生变化，只是由原来的一个数组全部元素参与异或运算，变成了两个数组中的元素都要参与异或运算，其实现代码如下：

(未完待续...)

如想系统学习Java编程，可以点击这里观看我在本站的视频课程，有问题也可以加入我的QQ群291839907一起讨论。