用位運算解決問題:1.不用循環,判斷一個數是2的n次方;2.不借助輔助變量,實作兩個數的交換。
位運算的巧妙應用
位運算的符号
與運算:&
或運算:|
異或運算:^
非運算:~
移位運算:>>和<<
判斷一個數是否是2的N次方
題目要求:用一個表達式,判斷一個數X是否是2的N次方,即2,4,8,16……等,要求不可以用循環語句。
解析:2,4,8,16這樣的數轉化成二進制是10,100,1000,10000。
如果X減去1後(低一位并且二進制的每一位都是1),這個數與X做與運算,答案若是0,則X是2的N次方。
是以答案是:!(X&(X-1))
兩個數的交換
題目要求:将a,b兩個數的值進行交換,并且不使用任何的中間變量。
解法1:
a = a+b;
b = a-b;
a = a-b;
這樣做的缺點就是如果a,b都是比較大的兩個數,a = a+b;時就會越界。
解法2:采用異或位運算。
異或運算:相同為0,相異為1。
a = a^b;//a變為一個相同為0,相異為1的結果
b = a^b;//該結果和b做運算,得到原來的a
a = a^b;//該結果和a做運算,得到原來的b
這裡稍微有點繞,我來詳細解釋一下:
首先,兩個數做異或運算,得到一個結果,這個結果中,原來兩個數相同的位被置為0,相異的位被置為1;
然後,這個結果和原來的b做異或運算,對每一位來說:
if(結果位為1)
{
//原來的a和b此位置相異
if(b此位為1)
{
a此位為0
}
else
{
a此位為1
}
}
if(結果位為0)
{
//原來的a和b此位置相同
if(b此位為1)
{
a此位為1
}
else
{
a此位為0
}
}
是以這個結果和原來的一個數做異或運算可以得到另一個數。
參考資料
《程式員面試寶典 第三版》第二部分 C++ 程式設計基本概念
作者: 聖騎士Wind
出處: 部落格園: 聖騎士Wind
Github: https://github.com/mengdd
微信公衆号: 聖騎士Wind