2021.05.07更新：添加異或運算的性質(zhì)
2020.03.23更新：添加位運算符~的應(yīng)用
2020.02.24更新：添加目錄、調(diào)整格式。
2020.01.04更新：反碼的缺點和使用，以及補碼的優(yōu)點。

---

文章目錄

• 一、前言
• 二、數(shù)的二進(jìn)制表示
• • 1. 原碼
  • 2. 反碼
  • 3. 補碼
• 三、運算符
• • 1. 按位與 &
  • 2. 按位或 |
  • 3. 按位取反 ~
  • 4. 按位異或 ^
  • 4. 左移 <<
  • 5. 右移 >>

一、前言

之前大一上課的時候，老師說位運算不考，當(dāng)時就沒有認(rèn)真去學(xué)習(xí)。后來學(xué)算法的時候，發(fā)現(xiàn)大佬的代碼中總會摻雜著一些位運算操作，為了理解那些代碼，前前后后也看了幾次位運算操作，但是沒有很好地記錄下來。現(xiàn)在又遇到了，借此機會寫個總結(jié)。

由于位運算都是直接對整數(shù)在內(nèi)存中的二進(jìn)制數(shù)進(jìn)行操作的，所以位運算的效率會相對比較高。

二、數(shù)的二進(jìn)制表示

二進(jìn)制數(shù)最高位為符號位，0表示正，1表示負(fù)（一般我們都不寫出來）。所以C語言中的int（32位整數(shù)）的范圍是$?2^{31}$到$2^{31}?1$，第32位用來做符號位了。
正數(shù)的二進(jìn)制表示即為它的原碼，負(fù)數(shù)的二進(jìn)制表示為它的補碼。

1. 原碼

把一個整數(shù)的絕對值轉(zhuǎn)換為二進(jìn)制數(shù)，再加上符號位就是該整數(shù)的原碼。例如：
+9的原碼為0 0001001（即為+9的二進(jìn)制表示）
-9的原碼為1 0001001

2. 反碼

正數(shù)的反碼與它的原碼相同，負(fù)數(shù)的反碼符號位不變，數(shù)值部分為原碼的按位取反。例如：
+9的反碼為0 0001001
-9的反碼為1 1110110

由于反碼0的表示不唯一、表示數(shù)的范圍比補碼少一個最小負(fù)數(shù)、運算時必須考慮循環(huán)進(jìn)位，因此反碼在計算機中很少被使用，有時用作數(shù)碼變換的中間表示形式。

3. 補碼

正數(shù)的補碼與它的原碼相同，負(fù)數(shù)的補碼為它的反碼+1。例如：
+9的補碼為0 0001001
-9的補碼為1 1110111(即為-9的二進(jìn)制表示)

因為補碼0的表示是唯一的，于是減少了+0和-0之間的轉(zhuǎn)換；少占用了一個編碼表示，使得補碼能比原碼多表示一個最小負(fù)數(shù)。

三、運算符

1. 按位與 &

對兩個等長的（不夠在前面用0補）二進(jìn)制數(shù)進(jìn)行按位與運算，如果對應(yīng)位都為1，則該位為1，否則該位為0。
例如：求9&3，將它們轉(zhuǎn)換為二進(jìn)制數(shù)（以下都是先這樣操作）

1001 0011 ----- 0001

應(yīng)用：

通常我們可以用n&1來判斷n是奇數(shù)還是偶數(shù)，因為奇數(shù)的二進(jìn)制最后一位都是1。

#include <iostream> using namespace std; int main() {for (int i = 0; i < 10; i++)if (i & 1) cout << i << " ";return 0; }

輸出結(jié)果
1 3 5 7 9

用 n&(-n) 求非負(fù)數(shù)在二進(jìn)制表示下最低位1以及它后面的0構(gòu)成的數(shù)值。（這一求解應(yīng)用在樹狀數(shù)組中）

對于任意整數(shù) $x$，令 $x=x\&(x?1)$，該運算將 $x$ 的二進(jìn)制表示的最后一個 $1$ 變成 $0$。于是，我們可以利用該性質(zhì)快速求一個數(shù)二進(jìn)制位有多少個1。

#include <iostream> using namespace std; int main() {int x, i;cin >> x;for (i = 0; x != 0; i++)x &= (x - 1);cout << i << endl;return 0; }

2. 按位或 |

對兩個等長的（不夠在前面用0補）二進(jìn)制數(shù)進(jìn)行按位或運算，如果對應(yīng)位都為0，則該位為0，否則該位為1。
例如：求9|3

1001 0011 ----- 1011

3. 按位取反 ~

~a表示對a的二進(jìn)制表示的每一位進(jìn)行取反，即0變?yōu)?，1變?yōu)?。例如：求~9

1001 ----- 0110

應(yīng)用：
用于求相反數(shù)，公式為：~n + 1

#include <stdio.h> int main () {int n = 10;printf("%d ", ~n + 1);return 0; }

輸出結(jié)果
-10

4. 按位異或 ^

對等長二進(jìn)制模式按位或二進(jìn)制數(shù)的每一位執(zhí)行邏輯按位異或操作，操作的結(jié)果是如果某位不同則該位為1, 否則該位為0。
（摘自百度百科）

例如：求9^3（很多新手會誤以為是$9^3$）

1001 0011 ----- 1010

記 $\oplus$ 為異或運算，異或運算滿足以下性質(zhì)：

$x\oplus x=0$

$x\oplus y=y\oplus x$（交換律）；

$(x\oplus y)\oplus z=x\oplus (y\oplus z)$（結(jié)合律）；

$x\oplus y\oplus y=x$（自反性）；

$?i\in Z?i\in Z，有4i\oplus (4i+1)\oplus (4i+2)\oplus (4i+3)=0$

應(yīng)用：

利用按位異或的自反性，我們可以不需要用輔助變量也能實現(xiàn)兩個數(shù)的交換（裝逼用【被打】）#include <iostream> using namespace std; int main() {int a = 10, b = 5;a = a ^ b;b = a ^ b;a = a ^ b;cout << a << " " << b << endl;return 0; }

輸出結(jié)果
5 10

4. 左移 <<

a<<n 表示將 a 的二進(jìn)制表示數(shù)向左移動 n 位，即在后面添加 n 個 0。同樣，也就相當(dāng)于 a 乘以 $2^n$。

#include <iostream> using namespace std; int main() {for (int i = 0; i < 10; i++)cout << (1<<i) << " ";return 0; }

輸入結(jié)果
1 2 4 8 16 32 64 128 256 512

5. 右移 >>

a>>n 與上面的左移剛好相反，表示將a的二進(jìn)制表示數(shù)往右移動n位，即直接去掉a后面的n位，相當(dāng)于a除以 $2^n$。通常我們可以利用 n>>=1 來代替 n /= 2來提高運算效率。

總結(jié)

以上是生活随笔為你收集整理的C++描述的位运算总结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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