位操作（Bit Manipulation）可以有很多技巧，有一個(gè)叫做 Bit Twiddling Hacks 的網(wǎng)站收集了幾乎所有位操作的黑科技玩法

但是這些技巧大部分都過(guò)于晦澀，我覺(jué)得可以作為字典查閱，沒(méi)必要逐條深究。但我認(rèn)為那些有趣的、有用的位運(yùn)算技巧，是我們每個(gè)人需要掌握的。

所以本文由淺入深，先展示幾個(gè)有趣（但沒(méi)卵用）的位運(yùn)算技巧，然后再匯總幾個(gè)在算法題以及工程開(kāi)發(fā)中常用的位運(yùn)算技巧。

幾個(gè)有趣的位操作

利用或操作`|`和空格將英文字符轉(zhuǎn)換為小寫

('a'|'')='a'
('A'|'')='a'

利用與操作`&`和下劃線將英文字符轉(zhuǎn)換為大寫

('b'&'_')='B'
('B'&'_')='B'

利用異或操作`^`和空格進(jìn)行英文字符大小寫互換

('d'^'')='D'
('D'^'')='d'

以上操作能夠產(chǎn)生奇特效果的原因在于 ASCII 編碼。ASCII 字符其實(shí)就是數(shù)字，恰巧空格和下劃線對(duì)應(yīng)的數(shù)字通過(guò)位運(yùn)算就能改變大小寫。有興趣的讀者可以查 ASCII 碼表自己算算，本文就不展開(kāi)講了。

不用臨時(shí)變量交換兩個(gè)數(shù)

inta=1,b=2;
a^=b;
b^=a;
a^=b;
//現(xiàn)在a=2,b=1

加一

intn=1;
n=-~n;
//現(xiàn)在n=2

減一

intn=2;
n=~-n;
//現(xiàn)在n=1

判斷兩個(gè)數(shù)是否異號(hào)

intx=-1,y=2;
booleanf=((x^y)

	

	如果說(shuō)前 6 個(gè)技巧的用處不大，這第 7 個(gè)技巧還是比較實(shí)用的，利用的是補(bǔ)碼編碼的符號(hào)位。整數(shù)編碼最高位是符號(hào)位，負(fù)數(shù)的符號(hào)位是 1，非負(fù)數(shù)的符號(hào)位是 0，再借助異或的特性，可以判斷出兩個(gè)數(shù)字是否異號(hào)。

	當(dāng)然，如果不用位運(yùn)算來(lái)判斷是否異號(hào)，需要使用 if else 分支，還挺麻煩的。你可能想利用乘積來(lái)判斷兩個(gè)數(shù)是否異號(hào)，但是這種處理方式容易造成整型溢出，從而出現(xiàn)錯(cuò)誤。

	index & (arr.length - 1) 的運(yùn)用

	我在單調(diào)棧解題套路中介紹過(guò)環(huán)形數(shù)組，其實(shí)就是利用求模（余數(shù)）的方式讓數(shù)組看起來(lái)頭尾相接形成一個(gè)環(huán)形，永遠(yuǎn)都走不完：

	
int[]arr={1,2,3,4};
intindex=0;
while(true){
//在環(huán)形數(shù)組中轉(zhuǎn)圈
print(arr[index%arr.length]);
index++;
}
//輸出：1,2,3,4,1,2,3,4,1,2,3,4...


	

	但模運(yùn)算%對(duì)計(jì)算機(jī)來(lái)說(shuō)其實(shí)是一個(gè)比較昂貴的操作，所以我們可以用&運(yùn)算來(lái)求余數(shù)：

	
int[]arr={1,2,3,4};
intindex=0;
while(true){
//在環(huán)形數(shù)組中轉(zhuǎn)圈
print(arr[index&(arr.length-1)]);
index++;
}
//輸出：1,2,3,4,1,2,3,4,1,2,3,4...


	

	簡(jiǎn)單說(shuō)，& (arr.length - 1)這個(gè)位運(yùn)算能夠替代% arr.length的模運(yùn)算，性能會(huì)更好一些。

	那問(wèn)題來(lái)了，現(xiàn)在是不斷地index++，你做到了循環(huán)遍歷。但如果不斷地index--，還能做到環(huán)形數(shù)組的效果嗎？

	答案是，如果你使用%求模的方式，那么當(dāng)index小于 0 之后求模的結(jié)果也會(huì)出現(xiàn)負(fù)數(shù)，你需要特殊處理。但通過(guò)&與運(yùn)算的方式，index不會(huì)出現(xiàn)負(fù)數(shù)，依然可以正常工作：

	
int[]arr={1,2,3,4};
intindex=0;
while(true){
//在環(huán)形數(shù)組中轉(zhuǎn)圈
print(arr[index&(arr.length-1)]);
index--;
}
//輸出：1,4,3,2,1,4,3,2,1,4,3,2,1...


	

	我們自己寫代碼一般用不到這個(gè)技巧，但在學(xué)習(xí)一些其他代碼庫(kù)時(shí)可能會(huì)經(jīng)?？吹?，這里留個(gè)印象，到時(shí)候就不會(huì)懵逼了。

	n & (n-1) 的運(yùn)用

	n & (n-1)這個(gè)操作在算法中比較常見(jiàn)，作用是消除數(shù)字n的二進(jìn)制表示中的最后一個(gè) 1。

	看個(gè)圖就很容易理解了：

	

	其核心邏輯就是，n - 1一定可以消除最后一個(gè) 1，同時(shí)把其后的 0 都變成 1，這樣再和n做一次&運(yùn)算，就可以僅僅把最后一個(gè) 1 變成 0 了。

	1、計(jì)算漢明權(quán)重（Hamming Weight）

	這是力扣第 191 題「位 1 的個(gè)數(shù)」：

	

	就是讓你返回n的二進(jìn)制表示中有幾個(gè) 1。因?yàn)閚 & (n - 1)可以消除最后一個(gè) 1，所以可以用一個(gè)循環(huán)不停地消除 1 同時(shí)計(jì)數(shù)，直到n變成 0 為止。

	
inthammingWeight(intn){
intres=0;
while(n!=0){
n=n&(n-1);
res++;
}
returnres;
}


	

	2、判斷一個(gè)數(shù)是不是 2 的指數(shù)

	力扣第 231 題「2 的冪」就是這個(gè)問(wèn)題。

	一個(gè)數(shù)如果是 2 的指數(shù)，那么它的二進(jìn)制表示一定只含有一個(gè) 1：

	
2^0=1=0b0001
2^1=2=0b0010
2^2=4=0b0100


	

	如果使用n & (n-1)的技巧就很簡(jiǎn)單了（注意運(yùn)算符優(yōu)先級(jí)，括號(hào)不可以省略）：

	
booleanisPowerOfTwo(intn){
if(n<=?0)?return?false;
????return?(n?&?(n?-?1))?==?0;
}


	

	a ^ a = 0 的運(yùn)用

	異或運(yùn)算的性質(zhì)是需要我們牢記的：

	一個(gè)數(shù)和它本身做異或運(yùn)算結(jié)果為 0，即a ^ a = 0；一個(gè)數(shù)和 0 做異或運(yùn)算的結(jié)果為它本身，即a ^ 0 = a。

	1、查找只出現(xiàn)一次的元素

	這是力扣第 136 題「只出現(xiàn)一次的數(shù)字」：

	

	對(duì)于這道題目，我們只要把所有數(shù)字進(jìn)行異或，成對(duì)兒的數(shù)字就會(huì)變成 0，落單的數(shù)字和 0 做異或還是它本身，所以最后異或的結(jié)果就是只出現(xiàn)一次的元素：

	
intsingleNumber(int[]nums){
intres=0;
for(intn:nums){
res^=n;
}
returnres;
}


	

	2、尋找缺失的元素

	這是力扣第 268 題「丟失的數(shù)字」：

	

	給一個(gè)長(zhǎng)度為n的數(shù)組，其索引應(yīng)該在[0,n)，但是現(xiàn)在你要裝進(jìn)去n + 1個(gè)元素[0,n]，那么肯定有一個(gè)元素裝不下嘛，請(qǐng)你找出這個(gè)缺失的元素。

	這道題不難的，我們應(yīng)該很容易想到，把這個(gè)數(shù)組排個(gè)序，然后遍歷一遍，不就很容易找到缺失的那個(gè)元素了嗎？

	或者說(shuō)，借助數(shù)據(jù)結(jié)構(gòu)的特性，用一個(gè) HashSet 把數(shù)組里出現(xiàn)的數(shù)字都儲(chǔ)存下來(lái)，再遍歷[0,n]之間的數(shù)字，去 HashSet 中查詢，也可以很容易查出那個(gè)缺失的元素。

	排序解法的時(shí)間復(fù)雜度是 O(NlogN)，HashSet 的解法時(shí)間復(fù)雜度是 O(N)，但是還需要 O(N) 的空間復(fù)雜度存儲(chǔ) HashSet。

	這個(gè)問(wèn)題其實(shí)還有一個(gè)特別簡(jiǎn)單的解法：等差數(shù)列求和公式。

	題目的意思可以這樣理解：現(xiàn)在有個(gè)等差數(shù)列0, 1, 2,..., n，其中少了某一個(gè)數(shù)字，請(qǐng)你把它找出來(lái)。那這個(gè)數(shù)字不就是sum(0,1,..n) - sum(nums)嘛？

	
intmissingNumber(int[]nums){
intn=nums.length;
//雖然題目給的數(shù)據(jù)范圍不大，但嚴(yán)謹(jǐn)起見(jiàn)，用long類型防止整型溢出
//求和公式：(首項(xiàng)+末項(xiàng))*項(xiàng)數(shù)/ 2
longexpect=(0+n)*(n+1)/2;
longsum=0;
for(intx:nums){
sum+=x;
}
return(int)(expect-sum);
}


	

	不過(guò)，本文的主題是位運(yùn)算，我們來(lái)講講如何利用位運(yùn)算技巧來(lái)解決這道題。

	再回顧一下異或運(yùn)算的性質(zhì)：一個(gè)數(shù)和它本身做異或運(yùn)算結(jié)果為 0，一個(gè)數(shù)和 0 做異或運(yùn)算還是它本身。

	而且異或運(yùn)算滿足交換律和結(jié)合律，也就是說(shuō)：

	
2^3^2=3^(2^2)=3^0=3


	

	而這道題索就可以通過(guò)這些性質(zhì)巧妙算出缺失的那個(gè)元素，比如說(shuō)nums = [0,3,1,4]：

	

	為了容易理解，我們假設(shè)先把索引補(bǔ)一位，然后讓每個(gè)元素和自己相等的索引相對(duì)應(yīng)：

	

	這樣做了之后，就可以發(fā)現(xiàn)除了缺失元素之外，所有的索引和元素都組成一對(duì)兒了，現(xiàn)在如果把這個(gè)落單的索引 2 找出來(lái)，也就找到了缺失的那個(gè)元素。

	如何找這個(gè)落單的數(shù)字呢，只要把所有的元素和索引做異或運(yùn)算，成對(duì)兒的數(shù)字都會(huì)消為 0，只有這個(gè)落單的元素會(huì)剩下，也就達(dá)到了我們的目的：

	
intmissingNumber(int[]nums){
intn=nums.length;
intres=0;
//先和新補(bǔ)的索引異或一下
res^=n;
//和其他的元素、索引做異或
for(inti=0;i

	

	由于異或運(yùn)算滿足交換律和結(jié)合律，所以總是能把成對(duì)兒的數(shù)字消去，留下缺失的那個(gè)元素。

	到這里，常見(jiàn)的位運(yùn)算差不多都講完了。這些技巧就是會(huì)者不難難者不會(huì)，也不需要死記硬背，只要有個(gè)印象就完全夠用了。

	




	審核編輯：劉清