原創(chuàng)公眾號(hào)：bigsai
原創(chuàng)不易，如果有收獲請(qǐng)不要吝嗇你的贊贊！
文章已收錄在 全網(wǎng)都在關(guān)注的數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)倉庫 歡迎star

前言

位運(yùn)算隱藏在編程語言的角落中，其神秘而又強(qiáng)大，暗藏內(nèi)力，有些人光聽位運(yùn)算的大名的心中忐忑，還有些人更是一看到位運(yùn)算就遠(yuǎn)遠(yuǎn)離去，我之前也是。但狡猾的面試官往往喜歡搞偷襲，抓住我們的弱點(diǎn)搞我們，為了防患于未然，特記此篇！

本篇的內(nèi)容為位運(yùn)算的介紹和一些比較經(jīng)典的位運(yùn)算問題進(jìn)行介紹分析，當(dāng)然，位運(yùn)算這么牛，后面肯定還是要?dú)w納總結(jié)的。

認(rèn)識(shí)位運(yùn)算

什么是位運(yùn)算？

程序中的所有數(shù)在計(jì)算機(jī)內(nèi)存中都是以二進(jìn)制的形式儲(chǔ)存的。位運(yùn)算就是直接對(duì)整數(shù)在內(nèi)存中的二進(jìn)制位進(jìn)行操作。

位運(yùn)算就是直接操作二進(jìn)制數(shù)，那么有哪些種類的位運(yùn)算呢？

常見的運(yùn)算符有與(&)、或(|)、異或(^)、取反(~)、左移(<<)、右移(>>是帶符號(hào)右移 >>>無符號(hào)右移動(dòng))。下面來細(xì)看看每一種位運(yùn)算的規(guī)則。

位運(yùn)算 & (與)

規(guī)則：二進(jìn)制對(duì)應(yīng)位兩兩進(jìn)行邏輯AND運(yùn)算(只有對(duì)應(yīng)位的值都是 1 時(shí)結(jié)果才為 1, 否則即為 0)即 0&0=0,0&1=0,1&1=1

例如：2 & -2

位運(yùn)算 | (或)

規(guī)則：二進(jìn)制對(duì)應(yīng)位兩兩進(jìn)行邏輯或運(yùn)算(對(duì)應(yīng)位中有一 個(gè)為1則為1) 即0|0=0,0|1=1,1|1=1

例如：2 | -2

位運(yùn)算 ^ (異或)

規(guī)則：二進(jìn)制對(duì)應(yīng)位兩兩進(jìn)行邏輯XOR (異或) 的運(yùn)算(當(dāng)對(duì)應(yīng)位的值不同時(shí)為 1, 否則為 0)即0^0=0, 0^1=1, 1^1=0

例如：2 ^ -2

按位取反~

規(guī)則：二進(jìn)制的0變成1，1變成0。

移位運(yùn)算符

左移運(yùn)算<<：左移后右邊位補(bǔ) 0

右移運(yùn)算>>：右移后左邊位補(bǔ)原最左位值(可能是0，可能是1)

右移運(yùn)算>>>：右移后左邊位補(bǔ) 0

• 對(duì)于左移運(yùn)算符<<沒有懸念右側(cè)填個(gè)零無論正負(fù)數(shù)相當(dāng)于整個(gè)數(shù)乘以2。

• 而右移運(yùn)算符就有分歧了，分別是左側(cè)補(bǔ)0>>>和左側(cè)補(bǔ)原始位>>，如果是正數(shù)沒爭議左側(cè)都是補(bǔ)0，達(dá)到除以2的效果；如果是負(fù)數(shù)的話左側(cè)補(bǔ)0>>>那么數(shù)值的正負(fù)會(huì)發(fā)生改變，會(huì)從一個(gè)負(fù)數(shù)變成一個(gè)相對(duì)較大的正數(shù)。而如果是左側(cè)補(bǔ)原始位(負(fù)數(shù)補(bǔ)1)>>那么整個(gè)數(shù)還是負(fù)數(shù)，也就是相當(dāng)于除以2的效果。

下面這張圖可以很好的幫助你理解負(fù)數(shù)的移位運(yùn)算符：

到這里，我想你應(yīng)該對(duì)位運(yùn)算有了初步的認(rèn)識(shí)，在這里把上面提到的部分案例執(zhí)行對(duì)比一下讓你看一下可能會(huì)理解的更清晰：

位運(yùn)算小技巧

在這里有些常用的位運(yùn)算小技巧。

判斷奇偶數(shù)

正常判斷奇數(shù)偶數(shù)的時(shí)候我們會(huì)這樣寫：

if( n % 2 == 1)// n 是個(gè)奇數(shù) }

使用位運(yùn)算可以這么寫：

if(n & 1 == 1){// n 是個(gè)奇數(shù)。 }

其核心就是判斷二進(jìn)制的最后一位是否為1，如果為1那么結(jié)果加上2^0=1一定是個(gè)奇數(shù)，否則就是個(gè)偶數(shù)。

交換兩個(gè)數(shù)

對(duì)于傳統(tǒng)的交換兩個(gè)數(shù)，我們需要使用一個(gè)變量來輔助完成操作，可能會(huì)是這樣：

int team = a; a = b; b = team;

但是使用位運(yùn)算可以不需要借助額外空間完成數(shù)值交換：

a=a^b;//a=a^b b=a^b;//b=(a^b)^b=a^0=a a=a^b;//a=(a^b)^(a^b^b)=0^b=b

原理已經(jīng)寫在注釋里面了，是不是感覺非常diao呢？

二進(jìn)制枚舉

在遇到子集問題的處理時(shí)候，我們有時(shí)候會(huì)借助二進(jìn)制枚舉來遍歷各種狀態(tài)(效率大于dfs回溯)。這種就屬于排列組合的問題了，對(duì)于每個(gè)物品(位置)來說，就是使用和不使用的兩個(gè)狀態(tài)，而在二進(jìn)制中剛好可以用1和0來表示。而在實(shí)現(xiàn)上，通過枚舉數(shù)字范圍分析每個(gè)二進(jìn)制數(shù)字各符號(hào)位上的特征進(jìn)行計(jì)算求解操作即可。

二進(jìn)制枚舉的代碼實(shí)現(xiàn)為：

for(int i = 0; i < (1<<n); i++) //從0～2^n-1個(gè)狀態(tài) {for(int j = 0; j < n; j++) //遍歷二進(jìn)制的每一位 共n位{if(i & (1 << j))//判斷二進(jìn)制數(shù)字i的第j位是否存在{//操作或者輸出}} }

位運(yùn)算經(jīng)典問題

有了上面的位運(yùn)算基礎(chǔ)，我們?cè)趺从梦贿\(yùn)算處理實(shí)際問題呢？或者有哪些經(jīng)典的問題可以用位運(yùn)算來解決呢。

不用加減乘除做加法

題目描述

寫一個(gè)函數(shù)，求兩個(gè)整數(shù)之和，要求在函數(shù)體內(nèi)不得使用+、-、*、/四則運(yùn)算符號(hào)。

分析：
這道題咋一聽可能沒啥思路，簡單研究一下位運(yùn)算還是能獨(dú)立推出來和理解的。

當(dāng)然，解決這題前，需要了解上面的四種位運(yùn)算。還要知道二進(jìn)制的運(yùn)算：0+0=0，0+1=1,1+1=0(進(jìn)位)

對(duì)于加法的一個(gè)二進(jìn)制運(yùn)算。如果不進(jìn)位那么就是非常容易的。這時(shí)候相同位都為0則為0，0和1則為1.滿足這種運(yùn)算的異或(不相同取1，相同取0)和或(有一個(gè)1則為1)都能滿足.

但事實(shí)肯定有進(jìn)位的運(yùn)算啊！看到上面操作的不足之后，我們肯定還需要解決進(jìn)位的問題對(duì)于進(jìn)位的兩數(shù)相加，這種核心思想為：

• 用兩個(gè)數(shù)，一個(gè)正常m相加(不考慮進(jìn)位的)。用異或a^b就是滿足這種要求，先不考慮進(jìn)位(如果沒進(jìn)位那么就是最終結(jié)果)。另一個(gè)專門考慮進(jìn)位的n。兩個(gè)1需要進(jìn)位。所以我們用a&b與記錄需要進(jìn)位的。但是還有個(gè)問題，進(jìn)位的要往上面進(jìn)位，所以就變成這個(gè)需要進(jìn)位的數(shù)左移一位。
• 然后就變成m+n重新迭代開始上面直到不需要進(jìn)位的(即n=0時(shí)候)。

實(shí)現(xiàn)代碼為：

public class Solution {public int Add(int num1,int num2) {/** 5+3 5^3(0110) 5&3(0001) * 0101 * 0011 */int a=num1^num2;int b=num1&num2;b=b<<1;if(b==0)return a;else {return Add(a, b);} } }

當(dāng)然，這里也可以科普一下二進(jìn)制求加法：average = （a&b） + ((a^b)>>1) ;

二進(jìn)制中1的個(gè)數(shù)

這是一道經(jīng)典題，在劍指offer上也有對(duì)應(yīng)題目，其具體題目要求輸入一個(gè)整數(shù)，輸出該數(shù)二進(jìn)制表示中1的個(gè)數(shù)(其中負(fù)數(shù)用補(bǔ)碼表示)。

對(duì)于這個(gè)問題，不用位運(yùn)算將它轉(zhuǎn)成二進(jìn)制字符串直接枚舉字符’1’的個(gè)數(shù)也可以直接求出來，但是這樣做是沒有靈魂的并且效率比較差。這里提供兩種解決思路

法一： 大家知道每個(gè)類型的數(shù)據(jù)它的背后實(shí)際都是二進(jìn)制操作。大家知道int的數(shù)據(jù)類型的范圍是(-2^31,231 -1)。并且int有32位。但是并非32位全部用來表示數(shù)據(jù)。真正用來表示數(shù)據(jù)大小的也是31位。最高位用來表示正負(fù)。

首先要知道：

1<<0=1 =00000000000000000000000000000001
1<<1=2 =00000000000000000000000000000010
1<<2=4 =00000000000000000000000000000100
1<<3=8 =00000000000000000000000000001000
. . . . . .
1<<30=2^30 =01000000000000000000000000000000
1<<31=-2^31 =10000000000000000000000000000000

其次還要知道位運(yùn)算&與。兩個(gè)十進(jìn)制與運(yùn)算.每一位同1為1。所以我們用2的正數(shù)次冪與知道的數(shù)分別進(jìn)行與運(yùn)算操作。如果結(jié)果不為0，那么就說明這位為1.(前面31個(gè)都是大于0的最后一個(gè)與結(jié)果是負(fù)數(shù)但是如果該位為1那么結(jié)果肯定不為0)

具體代碼實(shí)現(xiàn)為：

public int NumberOf1(int n) {int va=0;for(int i=0;i<32;i++){if((n&(1<<i))!=0){ va++;}}return va; }

法二是運(yùn)用n&(n-1)。n如果不為0，那么n-1就是二進(jìn)制第一個(gè)為1的變?yōu)?，后面全為1.這樣的n&(n-1)一次運(yùn)算就相當(dāng)于把最后一個(gè)1變成0.這樣一直到運(yùn)算的數(shù)為0停止計(jì)算次數(shù)就好了，如下圖共進(jìn)行三次運(yùn)算那么n的二進(jìn)制中就有三個(gè)1。

實(shí)現(xiàn)代碼為：

public class Solution {public int NumberOf1(int n) {int count=0;while (n!=0) {n=n&(n-1);count++;}return count;} }

只出現(xiàn)一次的(一個(gè))數(shù)字①

問題描述：

給定一個(gè)非空整數(shù)數(shù)組，除了某個(gè)元素只出現(xiàn)一次以外，其余每個(gè)元素均出現(xiàn)兩次。找出那個(gè)只出現(xiàn)了一次的元素。

說明：你的算法應(yīng)該具有線性時(shí)間復(fù)雜度。 你可以不使用額外空間來實(shí)現(xiàn)嗎？

分析：

這是一道簡單的面試題，面試官常問怎么樣用不太復(fù)雜的方法找出數(shù)組中僅出現(xiàn)一次的數(shù)字(其他均出現(xiàn)兩次)，暴力枚舉或者使用其他的存儲(chǔ)結(jié)構(gòu)都不夠優(yōu)化，而這個(gè)問題最高效的答案就是使用位運(yùn)算。首先你要注意兩點(diǎn)：

• 0和任意數(shù)字進(jìn)行異或操作結(jié)果為數(shù)字本身.
• 兩個(gè)相同的數(shù)字進(jìn)行異或的結(jié)果為0.

具體的操作就是用0開始和數(shù)組中每個(gè)數(shù)進(jìn)行異或，得到的值和下個(gè)數(shù)進(jìn)行異或，最終獲得的值就是出現(xiàn)一次(奇數(shù)次)的值。

class Solution {public int singleNumber(int[] nums) {int value=0;for(int i=0;i<nums.length;i++){value^=nums[i];}return value;} }

只出現(xiàn)一次的(一個(gè))數(shù)字②

問題描述：

給定一個(gè)非空整數(shù)數(shù)組，除了某個(gè)元素只出現(xiàn)一次以外，其余每個(gè)元素均出現(xiàn)了三次。找出那個(gè)只出現(xiàn)了一次的元素。

說明：你的算法應(yīng)該具有線性時(shí)間復(fù)雜度。 你可以不使用額外空間來實(shí)現(xiàn)嗎？

分析：

這題和上一題的思路略有不同，這題其他數(shù)字出現(xiàn)了3次，那么我們?nèi)绻苯邮褂梦贿\(yùn)算異或操作的話無法直接找到結(jié)果，就需要巧妙的運(yùn)用二進(jìn)制的其他特性：判斷整除求余操作。即判斷所有數(shù)字二進(jìn)制1的總個(gè)數(shù)和0的總個(gè)數(shù)一定有一個(gè)不是三的整數(shù)倍，如果0不是三的整數(shù)倍那么就說明結(jié)果的該位二進(jìn)制數(shù)字為0，同理否則為1.

在具體的操作實(shí)現(xiàn)上，問題中給出數(shù)組中的數(shù)據(jù)在int范圍之內(nèi)，那么我們就可以在實(shí)現(xiàn)上可以對(duì)int的32個(gè)位每個(gè)位進(jìn)行依次判斷該位1的個(gè)數(shù)求余3后是否為1，如果為1說明結(jié)果該位二進(jìn)制為1可以將結(jié)果加上去。最終得到的值即為答案。

具體代碼為：

class Solution {public int singleNumber(int[] nums) {int value=0;for(int i=0;i<32;i++){int sum=0;for(int num:nums){if(((num>>i)&1)==1){sum++;}}if(sum%3==1)value+=(1<<i);}return value;} }

只出現(xiàn)一次的(兩個(gè))數(shù)字③

題目描述

一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次。請(qǐng)寫程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字。

思路：

上面的問題處理和理解起來可能比較容易，但是這個(gè)問題可能稍微復(fù)雜一點(diǎn)，但是這題可以通過特殊的手段轉(zhuǎn)化為上面只出現(xiàn)一次的一個(gè)數(shù)字問題來解決，當(dāng)然核心的位運(yùn)算也是異或^。

具體思路就是想辦法將數(shù)組邏輯上一分為二！先異或一遍到最后得到一個(gè)數(shù)，得到的肯定是a^b(假設(shè)兩個(gè)數(shù)值分別為a和b)的值。在看異或^的屬性：不同為1，相同為0. 也就是說最終這個(gè)結(jié)果的二進(jìn)制為1的位置上a和b是不相同的。而我們可以找到這個(gè)第一個(gè)不同的位，然后將數(shù)組中的數(shù)分成兩份，該位為0的進(jìn)行異或求解得到其中一個(gè)結(jié)果a，該位為1的進(jìn)行異或求解得到另一個(gè)結(jié)果b。

具體可以參考下圖流程：

實(shí)現(xiàn)代碼為：

public int[] singleNumbers(int[] nums) {int value[]=new int[2];if(nums.length==2)return nums;int val=0;//異或求的值for(int i=0;i<nums.length;i++){val^=nums[i];}int index=getFirst1(val);int num1=0,num2=0;for(int i=0;i<nums.length;i++){if(((nums[i]>>index)&1)==0)//如果這個(gè)數(shù)第index為0 和num1異或num1^=nums[i];else//否則和 num2 異或num2^=nums[i];}value[0]=num1;value[1]=num2;return value; }private int getFirst1(int val) {int index=0;while (((val&1)==0&&index<32)){val>>=1;// val=val/2index++;}return index; }

結(jié)語

當(dāng)然，上面的問題可能有更好的解法，也有更多經(jīng)典位運(yùn)算問題將在后面歸納總結(jié)，希望本篇的位運(yùn)算介紹能夠讓你有所收獲，對(duì)位運(yùn)算能有更深一點(diǎn)的認(rèn)識(shí)。對(duì)于很多問題例如博弈問題等二進(jìn)制位運(yùn)算能夠很巧妙的解決問題，日后也會(huì)分享相關(guān)內(nèi)容，敬請(qǐng)期待！

原創(chuàng)不易，如果覺得有所收獲，希望大家點(diǎn)贊、分享、在看一鍵三連幫忙擴(kuò)散，謝謝！

咱們下次再見！

總結(jié)

以上是生活随笔為你收集整理的【面试锦囊】位运算介绍与经典例题总结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。