Java位運(yùn)算實(shí)現(xiàn)方法

不借助中間變量交換兩個變量的值

通常情況下，我們要交換兩個變量的值都按如下步驟操作：

這種操作方式不難理解，實(shí)現(xiàn)交換變量值的關(guān)鍵點(diǎn)就在于中間變量c。而現(xiàn)在的題目要求是不借助中間變量來交換a和b的值。如果不使用位運(yùn)算的方式，同樣可以做到不借助中間變量交換兩個變量的值，其實(shí)現(xiàn)過程如下。

為了講解方便，我們把最初a與b的值稱之為原始a和原始b，3行代碼就是3步操作：
第1步：把原始a與原始b相加的和存儲到變量a中，變量b的值暫時沒有發(fā)生變化。
第2步：用這個和減去原始b，再賦值到變量b中，經(jīng)過這一步運(yùn)算，變量b中就保存了原始a的值。
第3步：用原始a、b之和減去原始a的值，就得到原始b，并且把這個值保存到變量a中。
通過以上3步就實(shí)現(xiàn)了a、b兩個變量在不借助中間變量的情況下進(jìn)行值的交換。這種算法雖然沒有借助中間變量，但有一個問題是如果a和b都是較大的數(shù)，在做第1步操作的時候就有可能出現(xiàn)兩值相加的和超出int類型的最大值，產(chǎn)生溢出的現(xiàn)象，從而導(dǎo)致后面的運(yùn)算全部出錯。
而我們用位運(yùn)算的方式實(shí)現(xiàn)交換，就不存在這個問題了。具體代碼如下：

講述這段代碼之前，先回顧一個運(yùn)算規(guī)律，那就是：a^b^b的運(yùn)算結(jié)果等于a。對此運(yùn)算規(guī)律有疑義，請閱讀《Java千問：Java語言位運(yùn)算符詳解》一文。為了表述方便，我們把a(bǔ)^b的操作稱之為”用b對a加密”，之所以這么稱呼，就是因?yàn)閍與b進(jìn)行了異或運(yùn)算之后，得到一個全新的值，效果如同對a加密一樣。而把a(bǔ)^b^b的操作稱之為”還原”， 之所以這么稱呼，就是因?yàn)閍^b^b的運(yùn)算結(jié)果等于a，如同是把a(bǔ)的值”加密”之后，又進(jìn)行了還原，恢復(fù)了a的值。
我們還是把a(bǔ)和b最初的值稱為原始a和原始b。這三行代碼是如何實(shí)現(xiàn)變量值交換的呢？我們逐行講解：
第1行代碼：對a用b進(jìn)行了加密操作，并且又賦值給了變量a，此時變量a就由原始數(shù)據(jù)變成了加密后的值。
第2行代碼：把加密后的值與原始b進(jìn)行異或運(yùn)算，就還原了原始a的值，我們把這個值賦值給b，這樣變量b中就存儲了原始a的值。
第3行代碼：用加密后的值與現(xiàn)在的b，也就是保存了原始a的變量進(jìn)行異或操作，就能得到原始b的值，之后再把原始b的值賦值給變量a，這樣就完成了變量a與b值的交換。

找出單身狗元素

所謂找出單身狗元素就是指：一個數(shù)組中，某個數(shù)只出現(xiàn)了一次，而其他數(shù)都出現(xiàn)了兩次，要求編寫程序把那個只出現(xiàn)了一次的數(shù)找出來。完成這個題目的最核心原理就是: 兩個相同的數(shù)字進(jìn)行異或運(yùn)算，結(jié)果為0，而任何一個整數(shù)與0進(jìn)行異或運(yùn)算，其結(jié)果都是這個數(shù)本身。另外，任意N個整數(shù)進(jìn)行異或操作，滿足交換律。
按照這個思路，我們只需要把數(shù)組中所有的元素都做一遍異或操作，所得到的值就是那個只出現(xiàn)了一次的數(shù)字。因?yàn)槌霈F(xiàn)了兩次的數(shù)字，它們之間進(jìn)行異或操作會變?yōu)?。即使這兩個數(shù)字沒有挨在一起，但根據(jù)異或運(yùn)算的交換律我們可以知道：位置關(guān)系并不影響運(yùn)算結(jié)果，所以兩個相同的數(shù)字只要都參與了異或運(yùn)算，最終的結(jié)果都是0。而那個只出現(xiàn)了一次的數(shù)字，與0進(jìn)行異或操作，其結(jié)果仍然是它自身的值。因此，異或運(yùn)算的結(jié)果就是那個只出現(xiàn)了一次的數(shù)字，我們根據(jù)異或運(yùn)算的結(jié)果，就能找出”單身狗”元素了。具體實(shí)現(xiàn)代碼如下：

這道題目還有另一個版本，題目描述為：有整型數(shù)組a和b，a數(shù)組中所有元素都出現(xiàn)在b數(shù)組中，但b數(shù)組比a數(shù)組多出一個元素，編寫程序找到b數(shù)組中多出來的這個元素。雖然變成了兩個數(shù)組，但實(shí)現(xiàn)算法的思路并沒有發(fā)生變化，只是由原來的一個數(shù)組全部元素參與異或運(yùn)算，變成了兩個數(shù)組中的元素都要參與異或運(yùn)算，其實(shí)現(xiàn)代碼如下：