開啟章節選單

位元運算

罕見

C++ 中的十進制轉二進制及位元運算

有的時候，程式運算並不僅僅侷限於十進制的運算。事實上，在程式的世界，可以用很多不一樣的進制處理數字，好比說二進制、八進制、十六進制等等，接下來將會先簡單的介紹二進制跟怎麼轉換它。

十進制轉二進制

要將一個十進制數字轉換為二進制表示，我們可以重複地將該數字除以 2 ，直到商為 0 ，然後將所有餘數串連起來，從低位到高位排列即可。好比說如果你想知道 10 的二進制表示法，你可以這樣做：

1. 10 / 2 = 5 ， 10 % 2 = 0      // 目前二進制： 0
2.  5 / 2 = 2 ， 5 % 2 = 1       // 目前二進制： 0 1
3.  2 / 2 = 1 ， 2 % 2 = 0       // 目前二進制： 0 1 0
4.  1 / 2 = 0 ， 1 % 2 = 1       // 目前二進制： 0 1 0 1
5. 逆轉餘數們                   　 // 最後二進制： 1 0 1 0

用程式碼來表示的話，可以這樣寫：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 10;

    // 存放二進制數字的 vector
    vector<int> binary;

    // 重複地將該數字除以 2，直到商為 0
    while (n > 0) {
        binary.push_back(n % 2); // 取餘數
        n /= 2;
    }

    // 反轉後輸出
    reverse(binary.begin(), binary.end());
    for (auto i : binary) {
        cout << i;
    }

    cout << endl;
}

二進制轉十進制

要將一個二進制數字轉換為十進制表示，我們可以遍歷二進制數字的每一位，並將第 i 位的值乘以 2 的 i 次方，然後將所有結果相加即可。好比說如果你想知道 1010 的十進制表示法，你可以這樣做：

1 * 2^3 + 0 * 2^2 + 1 * 2^1 + 0 * 2^0 = 8 + 0 + 2 + 0 = 10

用程式碼來表示的話，可以這樣寫：

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> binary = {1, 0, 1, 0};

    int decimal = 0;
    for (int i = 0; i < binary.size(); i++) {
        decimal += binary[i] * pow(2, binary.size() - i - 1);
    }

    cout << decimal << endl;
}

位元運算子

C++ 提供了以下位元運算子：

運算子描述語法
&位元 ANDA & B
|位元 ORA | B
^位元 XORA ^ B
~位元 NOT~A
<<左移位A << n
>>右移位A >> n

讓我們看一些具體的範例來了解這些運算子的用法。

位元 AND（&）

位元 AND 運算子將兩個操作數的對應位進行 AND 運算。AND 就是只有當兩個操作數的對應位都為 1 時，結果位才為 1，否則為 0。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a = 0b00010101;  // 二進制: 21
    int b = 0b00011010;  // 二進制: 26

    cout << "a & b = " << (a & b) << endl;  // 輸出: 16 (二進制: 00010000)
}

輸出：

a & b = 26

位元 OR（|）

位元 OR 運算子將兩個操作數的對應位進行 OR 運算。只要有一個操作數的對應位為 1，結果位就為 1，否則為 0。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a = 0b00010101;  // 二進制: 21
    int b = 0b00011010;  // 二進制: 26

    cout << "a | b = " <<（int)(a | b) << endl;  // 輸出: 31
}

輸出：

a | b = 31

位元 XOR（^）

位元 XOR 運算子將兩個操作數的對應位進行 XOR 運算。只有當兩個操作數的對應位不同時，結果位才為 1，否則為 0。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a = 0b00010101;  // 二進制: 21
    int b = 0b00011010;  // 二進制: 26

    cout << "a ^ b = " << (a ^ b) << endl;  // 輸出: 15
}

輸出：

a ^ b = 15

位元 NOT（~）

位元 NOT 運算子將操作數的每個位進行取反操作，即將 1 變為 0，將 0 變為 1。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a = 0b00000101;  // 二進制的 5

    cout << "~a = " << (~a) << endl;  // 輸出: -6
}

輸出：

~a = -6
為啥不是 -5 ？？？

大家有沒有好奇過負數都怎麼轉成二進位的？其實在程式裡，有一種東西叫做補數，詳細可以參考 這篇文章。

左移位（<<）

左移位運算子將一個數值的位模式向左移動指定的位數，舊位將被丟棄，新位將被填充 0 。左移位相當於乘以 2 的 n 次方。這步非常好用，尤其它可以省時間（* 耗時比 << 長）。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a = 0b00000101;  // 二進制: 5

    cout << "a << 2 = " << (a << 2) << endl;  // 輸出: 20
}

輸出：

a << 2 = 20

右移位（>>）

和左移位恰好相法，右移位運算子將一個數值的位模式向右移動指定的位數，舊位將被丟棄，新位將根據數值的符號被填充。對於正數，新位將被填充 0；對於負數，新位將被填充 1。右移位相當於整數除以 2 的 n 次方。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int b = 0b00001010;  // 二進制: 10

    cout << "b >> 1 = " << (b >> 1) << endl;  // 輸出: 5
}

輸出：

b >> 1 = 5

常見的位元運算操作

判斷某數是否為 2 的冪次方

要判斷一個數字是否為 2 的冪次方，可以使用位元運算。一個數字是 2 的冪次方，若且唯若它的二進制表示中只有一個 1。例如，4 的二進制表示是 100，8 的二進制表示是 1000，16 的二進制表示是 10000。

我們可以發現如果一個只有一個 1 的數字減去 1，那麽它的位數會少一，並且剩餘的位數都是 1。例如，8 的二進制表示是 1000，7 的二進制表示是 111，因此我們就可以把 8 和 7 進行 AND 運算，如果結果是 0，那麽這個數字就是 2 的冪次方。

bool is_power_of_two(int n) {
    return (n & (n - 1)) == 0;
}

int main() {
    cout << is_power_of_two(4) << endl;  // 輸出: 1
    cout << is_power_of_two(5) << endl;  // 輸出: 0
}

檢查奇偶

要檢查一個數字是奇數還是偶數，可以使用位元運算。一個數字是奇數還是偶數取決於它的最後一位是 0 還是 1。如果最後一位是 0，則該數字是偶數；如果最後一位是 1，則該數字是奇數。我們可以透過 AND 運算子 & 來檢查最後一位是 0 還是 1。

bool is_even(int n) {
    return (n & 1) == 0;
}

int main() {
    int a = 5;  // 二進制: 101
    int b = 6;  // 二進制: 110

    cout << is_even(a) << endl;  // 輸出: 0
    cout << is_even(b) << endl;  // 輸出: 1
}

這樣的優點是非常快速，比起 % 運算子，& 運算子的效率更高。

交換兩個數字

要交換兩個數字，可以使用 XOR 運算子 ^。這是因為 XOR 運算子有一個很有趣的性質：A ^ B ^ B = A。這意味著如果我們對 A 和 B 進行 XOR 運算，然後再對結果和 B 進行 XOR 運算，我們將得到 A。

void swap(int &a, int &b) {
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
}

int main() {
    int a = 5;  // 二進制: 101
    int b = 6;  // 二進制: 110

    swap(a, b);
    cout << a << " " << b << endl;  // 輸出: 6 5
}

當然這邊只是舉例，實際上我們可以直接使用內建的 swap 函式更方便：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a = 5;
    int b = 6;

    swap(a, b);
    cout << a << " " << b << endl;  // 輸出: 6 5
}

取得某個位元的值

要取得一個數字的某個位元的值，可以使用 AND 運算子 &。假設我們想要取得一個數字的第 i 個位元的值，我們可以將該數字和 1 << i 進行 AND 運算。

bool get_bit(int n, int i) {
    return (1 << i) & n;
}

int main() {
    int a = 5;  // 二進制: 101

    cout << get_bit(a, 0) << endl;  // 輸出: 1
    cout << get_bit(a, 1) << endl;  // 輸出: 0
    cout << get_bit(a, 2) << endl;  // 輸出: 1
}

把某個位元設定為 1

要把一個數字的某個位元設定為 1，可以使用 OR 運算子 |。假設我們想要把一個數字的第 i 個位元設定為 1，我們可以將該數字和 1 << i 進行 OR 運算。

int set_bit(int n, int i) {
    return (1 << i) | n;
}

int main() {
    int a = 5;  // 二進制: 101

    cout << set_bit(a, 1) << endl;  // 輸出: 7 (二進制: 111)
}

把某個位元設定為 0

要把一個數字的某個位元設定為 0，可以使用 AND 運算子 &。假設我們想要把一個數字的第 i 個位元設定為 0，我們可以將該數字和 ~(1 << i) 進行 AND 運算。

int clear_bit(int n, int i) {
    return ~(1 << i) & n;
}

int main() {
    int a = 5;  // 二進制: 101

    cout << clear_bit(a, 2) << endl;  // 輸出: 1 (二進制: 001)
}

把某個位元反轉

要把一個數字的某個位元反轉，可以使用 XOR 運算子 ^。假設我們想要把一個數字的第 i 個位元反轉，我們可以將該數字和 1 << i 進行 XOR 運算。

int flip_bit(int n, int i) {
    return (1 << i) ^ n;
}

int main() {
    int a = 5;  // 二進制: 101

    cout << flip_bit(a, 1) << endl;  // 輸出: 7 (二進制: 111)
}

小測驗

運算子 ^ 代表什麼意思？

練習題

位元運算大師解答