43      阿裏雲  技術社區[雲棲]

位運算小結操作

一、前言

輸入2 的n 次方： 
如果突然要你輸入2 的19 次方，你是不是還要想一下呢？敲個524288 多累啊。用位運算：1 << 19 又快又準。

乘除2 的倍數： 
千萬不要用乘除法，非常拖效率。隻要知道左移1 位就是乘以2 ，右移1 位就是除以2 就行了。
比如要算 25 * 4 ，用25 << 2 就好啦。

判斷偶數： 
a % 2 取模是最常用的判斷方法之一。這樣要用到除法運算，不好。實際上，還是用位運算解決：a & 1 。效果和a % 2 是一樣的，但是要快得多。

對2 的倍數取模： 
類似上麵的方法。對2 的倍數取模，隻要將數與2 的倍數-1 做與運算就可以了。如：
a % 8 = a & (8-1)
節省乘除法可以提高效率。

判斷一個整數是否是處於 0-65535 之間（常用的越界判斷）： 
用一般的 (a >= 0) && (a <= 65535) 可能要兩次判斷。
改用位運算隻要一次：
a & ~((1 << 16)-1)
後麵的常數是編譯時就算好了的。其實隻要進行一次與運算就行了。

算掩碼： 
比如一個截取低6 位的掩碼：0x3F
用位運算這麼表示：(1 << 6) - 1
這樣也非常好讀取掩碼，因為掩碼的位數直接體現在表達式裏。

二、位運算符

位運算方法有七種：

&   與運算： 當兩個位都為1 時結果為1 ，其它為0 。

|  或運算： 當兩個位都為0 時結果為0 ，其它為1 。

^  異或運算： 當兩個位數值不同時結果為1 ，相同為0 。

~  非運算( 求補) ： 位的值為1 時結果為0 ，位的值為0 時結果為1 。

<< 左移運算： 右邊空出的位上補0 ，左邊的位將從字頭擠掉，其值相當於乘2。

>>  右移運算： 右邊的位被擠掉。對於左邊移出的空位，如果是正數則空位補0，若為負數，可能補0 或補1 ，這取決於所用的計算機係統。

>>>   無符號右移運算： 右邊的位被擠掉，對於左邊移出的空位一概補上0 。



三、位運算應用口訣

清零取反要用與，某一位置可用或。

若要取反和交換，輕輕鬆鬆用異或。



四、需要注意的問題

1 、優先級

移位運算符, 單目取反運算符的優先級比比較運算符高。但是“& ”、“|”和“^ ”的優先級是比比較運算符低的，這點一定要注意。

如6 & 6 > 4 的結果是0 ， 而不是 true 。(6 & 6) > 4 的結果才是true ，所以要注意勤加括號。

2 、速度

位運算的速度是非常快的，你甚至可以忽略他的耗時，但是畢竟操作肯定是有耗損的。所以，應該盡量使用

“^= ”、“|= ”和“&= ”這樣的操作，比如說a ^= b ， 速度比 a = a ^ b快，因為前者是直接在a 上進行操作，而 a = a ^ b 的第二個a ，是一個a 的副本，可見在操作中程序對a 複製了一次，運算的結果又對原來的a 做了一次賦值

3 、範圍

要當心移位運算時發生範圍溢出。

4 、位數不同的運算數之間的運算規則

　　C 語言中，位運算的對象可以是整型（int ）和字符型（char ）數據。整形數據可以直接轉化成二進製數，字符型數據在內存中以它的ASCII 碼值存放，也可以轉化成二進製數。當兩個運算數類型不同時，位數亦會不同。遇到這種情況，係統將自動進行如下處理：將兩個運算數右端對齊，再將位數短的一個運算數往高位擴充，即：無符號數和正整數左側用0 補全; 負數左側用1 補全；然後對位數相等的兩個運算數，按位進行運算。



五、位運算的應用( 源操作數s ，掩碼mask) 

1 、按位與 &

清零特定位（mask 中特定位置0 ，其它位為1 ，s=s&mask ）

取某數中指定位（mask 中特定位置1 ，其它位為0 ，s=s&mask ）

2 、按位或 |

常用來將源操作數某些位的數值置1 ，其它位不變。（mask 中特定位置1 ，其它位為0 ，s=s|mask ）

3 、位異或 ^

使特定位的值取反（mask 中特定位置1 ，其它位為0 ，s=s^mask ）

不引入第三變量，交換兩個變量（a ，b ）的值

a = a ^ b;

b = a ^ b;

a = a ^ b;



六、二進製補碼運算公式

-x = ~x+1 = ~(x-1)
~x = -x-1
-(~x) = x+1
~(-x) = x-1
x+y = x-~y-1 = (x|y) + (x&y)
x-y = x+~y+1 = (x|~y) - (~x&y)
x^y = (x|y) - (x&y)
x|y = (x&~y) + y
x&y = (~x|y) - ~x
x==y : ~(x-y|y-x)
x!=y : x-y|y-x
x< y : (x-y)^((x^y)&((x-y)^x))
x<=y : (x|~y)&((x^y)|~(y-x))
x< y : (~x&y)|((~x|y)&(x-y))      // 無符號x,y 比較
x<=y : (~x|y)&((x^y)|~(y-x))      // 無符號x,y 比較



七、應用舉例

01 、判斷int 型變量a 是奇數還是偶數

a&1 = 0 偶數

a&1 = 1 奇數

02 、取int 型變量a 的第k 位 (k=0,1,2 ……sizeof(int)) ，即a>>k&1

03 、將int 型變量a 的第k 位清0 ，即a=a&~(1<<k)

04 、將int 型變量a 的第k 位置1 ， 即a=a|(1<<k)

05 、int 型變量循環左移k 次，即a=a<<k|a>>16-k ( 設sizeof(int)=16)

06 、int 型變量a 循環右移k 次，即a=a>>k|a<<16-k (設sizeof(int)=16)

07 、整數的平均值

對於兩個整數x 、y ，如果用 (x+y)/2 求平均值，會產生溢出，因為 x+y 可能會大於INT_MAX ，但是我們知道它們的平均值是肯定不會溢出的，我們用如下算法：

int average(int x,int y) // 返回X,Y 的平均值

{

    return (x&y)+((x^y)>>1);

}

08 、判斷一個整數是不是2 的冪

對於一個數 x >= 0 ，判斷它是不是2 的冪

boolean power2(int x)

{

    return ((x&(x-1))==0)&&(x!=0);

}

09 、 不用 temp 交換兩個整數

void swap(int x,int y)

{

  x ^= y;

  y ^= x;

  x ^= y;

}

10 、計算絕對值

int abs( int x )

{

    int y;

    y = x >> 31;

    return (x^y)-y ;  // 或者return (x+y)^y;

}

11 、取模運算轉化成位運算 ( 在不產生溢出的情況下)

a % (2^n) 等價於 a & (2^n - 1)

12 、乘法運算轉化成位運算 ( 在不產生溢出的情況下)

a * (2^n) 等價於 a<< n

13 、除法運算轉化成位運算 ( 在不產生溢出的情況下)

a / (2^n) 等價於 a>> n

例: 12/8 == 12>>3

14 、a % 2 等價於 a & 1

15 、

if(x==a)

    x=b;

else

    x=a;

等價於

x=a^b^x;

16 、x 的相反數表示為(~x+1)



八、實例

最後更新：2017-04-02 16:47:43

  上一篇： Android 4.1 Jelly Bean 相關資源

  下一篇： Android ActionBar 作為導航條的一個Bug