標簽：c++

位運算是一種針對二進制數的一種運算

位運算 共有六種

都有其對應得操作符號

& ? ?? (and)? ? ? 位于

| ? ? ?? (or) ???? ?? 位或

~ ? ?? (not) ? ? ?? 取反

^?????? (xor) ? ? ?? 異或

>>??? (shr)??? 右移一位

<< ?? (shl)???? 左移一位

運算說明：

=== 1. and運算 ===

and運算通常用于二進制取位操作，例如一個數 and 1的結果就是取二進制的最末位。這可以用來判斷一個整數的奇偶，二進制的最末位為0表示該數為偶數，最末位為1表示該數為奇數。

相同位的兩個數字都為1，則為1；若有一個不為1，則為0。

00101

11100

(&；或者and)

----------------

00100

=== 2. or運算 ===

or運算通常用于二進制特定位上的無條件賦值，例如一個數or 1的結果就是把二進制最末位強行變成1。如果需要把二進制最末位變成0，對這個數or 1之后再減一就可以了，其實際意義就是把這個數強行變成最接近的偶數。

相同位只要一個為1即為1。

00101

11100

(|或者or)

----------------

11101

=== 3. xor運算 ===

異或的符號是⊕。按位異或運算, 對等長二進制模式按位或二進制數的每一位執行邏輯按位異或操作. 操作的結果是如果某位不同則該位為1, 否則該位為0.

xor運算的逆運算是它本身，也就是說兩次異或同一個數最后結果不變，即(a xor b) xor b = a。xor運算可以用于簡單的加密，比如我想對我MM說1314520，但怕別人知道，于是雙方約定拿我的生日19880516作為密鑰。1314520 xor 19880516 = 20665500，我就把20665500告訴MM。MM再次計算20665500

xor 19880516的值，得到1314520，于是她就明白了我的企圖。

相同位不同則為1，相同則為0。

00101

11100

(^或者xor)

----------------

11001

運算結果

x

y

x

執行了第一句后x變成了x # y。那么第二句實質就是y

加法和減法互為逆運算，并且加法滿足交換律。把#換成+，把@換成-，我們可以寫出一個不需要臨時變量的swap過程(Pascal)。

procedure swap(var a,b:longint);

begin

a:=a + b;

b:=a - b;

a:=a - b;

end;

好了，剛才不是說xor的逆運算是它本身嗎？于是我們就有了一個看起來非常詭異的swap過程：

procedure swap(var a,b:longint);

begin

a:=a xor b;

b:=a xor b;

a:=a xor b;

end;

注意：位運算版本的交換兩數不適用于一個數的自我交換。也就是說，如果上述程序的“b”改成“a”的話，其結果是變量a變成零。因此，在使用快速排序時，由于涉及到一個數的自我交換，因此如果要在其中使用位運算版的交換兩數的話，應該先判斷。具體的時間損耗在此略過。

=== 4. not運算 ===

not運算的定義是把內存中的0和1全部取反。使用not運算時要格外小心，你需要注意整數類型有沒有符號。如果not的對象是無符號整數(不能表示負數)，那么得到的值就是它與該類型上界的差，因為無符號類型的數是用00到$FFFF依次表示的。下面的兩個程序(僅語言不同)均返回65535。

如果not的對象是有符號的整數，情況就不一樣了，稍后我們會在“整數類型的儲存”小節中提到。

=== 5. shl運算 ===

a shl b就表示把a轉為二進制后左移b位(在后面添b個0)。例如100的二進制為1100100，而110010000轉成二進制是400，那么100 shl 2 = 400。可以看出，a shl b的值實際上就是a乘以2的b次方，因為在二進制數后添一個0就相當于該數乘以2。

通常認為a shl 1比a * 2更快，因為前者是更底層一些的操作。因此程序中乘以2的操作請盡量用左移一位來代替。

定義一些常量可能會用到shl運算。你可以方便地用1 shl 16 - 1來表示65535。很多算法和數據結構要求數據規模必須是2的冪，此時可以用shl來定義Max_N等常量。

=== 6. shr運算 ===

和shl相似，a shr b表示二進制右移b位(去掉末b位)，相當于a除以2的b次方(取整)。我們也經常用shr 1來代替div 2，比如二分查找、堆的插入操作等等。想辦法用shr代替除法運算可以使程序效率大大提高。最大公約數的二進制算法用除以2操作來代替慢得出奇的mod運算，效率可以提高60%。

因為是最底層的運算? 所以相對常規運算 計算時間能減少很多

位運算加速技巧

1. 如果乘上一個2的倍數數值，可以改用左移運算(Left Shift) 加速 300%

x = x * 2;

x = x * 64;

//改為:

x = x << 1; // 2 = 21

x = x << 6; // 64 = 26

2. 如果除上一個 2 的倍數數值，可以改用右移運算加速 350%

x = x / 2;

x = x / 64;

//改為:

x = x >> 1;// 2 = 21

x = x >> 6;// 64 = 26

3. 數值轉整數加速 10%

x = int(1.232)

//改為:

x = 1.232 >> 0;

4. 交換兩個數值(swap)，使用 XOR 可以加速20%

var t:int = a;

a = b;

b = t;

//equals:

a = a^b;

b = a^b;

a = a^b;

5. 正負號轉換，可以加入 300%

i = -i;

//改為

i = ~i + 1; // NOT 寫法

//或

i = (i ^ -1) + 1; // XOR 寫法

6. 取余數，如果除數為 2 的倍數，可利用 AND 運算加速 600%

x = 131 % 4;

//equals:

x = 131 & (4 - 1);

7. 利用 AND 運算檢查整數是否為 2 的倍數，可以加速 600%

isEven = (i % 2) == 0;

//equals:

isEven = (i & 1) == 0;

8. 加速 Math.abs 600% 的寫法1，寫法2 又比寫法1加速 20%

//寫法1

i = x < 0 ? -x : x;

//寫法2

i = (x ^ (x >> 31)) - (x >> 31);

//寫法3

i=x^(~(x>>31)+1)+(x>>31);

9. 比較兩數值相乘之后是否擁有相同的符號，加速 35%

eqSign = a * b > 0;

//equals:

eqSign = a ^ b > 0;

標簽：c++

原文：http://blog.csdn.net/axuan_k/article/details/38371985

總結

以上是生活随笔為你收集整理的c语言位运算+乘法,关于c语言中的位运算。。。的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。