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++ 提供了以下位元運算子：
| 運算子 | 描述 | 語法 |
|---|---|---|
& | 位元 AND | A & B |
| | 位元 OR | A | B |
^ | 位元 XOR | A ^ 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)
}
