C. 位元運算
APCS 官方公告的檢測範圍裡，初級實作題那一欄單獨列了「位元運算」。正文的題目用不到它，所以留到這裡講。
電腦裡的整數是一串 0 與 1（上冊 2.2 的位元）。位元運算就是把兩個數字的位元對齊，一格一格分開算——12 與 10 對齊起來長這樣：
12 → 00001100
10 → 00001010¶六個運算子
a & b（AND）：兩邊同一格都是 1 才是 1a | b（OR）：兩邊同一格有一邊是 1 就是 1a ^ b（XOR，互斥或）：兩邊同一格不一樣才是 1~a（NOT）：每一格 0 換成 1、1 換成 0a << k（左移）：整排往左推 k 格，右邊補 0a >> k（右移）：整排往右推 k 格，推出界的丟掉
#include <iostream>
using namespace std;
// 印出 x 最低的 8 個位元（由高位印到低位），後面接十進位值
void print_bits(int x) {
for (int i = 7; i >= 0; i--) {
cout << ((x >> i) & 1);
}
cout << ' ' << x << '\n';
}
int main() {
int a = 12, b = 10;
print_bits(a); // a
print_bits(b); // b
print_bits(a & b); // 兩邊都是 1 才是 1
print_bits(a | b); // 有一邊是 1 就是 1
print_bits(a ^ b); // 兩邊不一樣才是 1
print_bits(a << 1); // 整排往左推一格
print_bits(a >> 1); // 整排往右推一格
cout << (~a) << '\n'; // 每一格 0 換成 1、1 換成 0
return 0;
}
執行結果：
00001100 12
00001010 10
00001000 8
00001110 14
00000110 6
00011000 24
00000110 6
-13前五行對照著看就清楚了：00001100 與 00001010 逐格比對，& 得到 00001000、| 得到 00001110、^ 得到 00000110。左移一格數字變兩倍、右移一格變一半，也在後兩行看得到。
最後一行的 ~a 印出 -13：int 有 32 個位元，最左邊那一格代表正負號，~ 連它一起翻面，正數就變成負數；翻面後的值固定是 -x - 1。
¶最常看到的三種用法
x & 1判奇偶：最低那一格就是除以 2 的餘數，是 1 代表奇數。1 << k就是 2^k：1只有最低一格是 1，往左推 k 格剛好是 2^k。x >> 1相當於除以 2（限非負整數，除不盡的部分直接捨去）；同理x >> k就是除以 2^k。
¶XOR 的兩個性質
a ^ a 一定是 0（每一格都跟自己一樣），a ^ 0 則是 a 本身。XOR 還可以交換、可以任意結合——一整串 XOR 起來，順序怎麼調換都不影響結果。
兩者合起來就有一個經典用法：一堆數字裡只有一個出現奇數次、其餘都成對，把全部 XOR 起來，成對的兩兩抵消，剩下的就是答案。
#include <iostream>
using namespace std;
int main() {
int n = 25;
cout << (n & 1) << ' ' << (24 & 1) << '\n'; // 判斷奇偶
cout << (1 << 0) << ' ' << (1 << 3) << ' ' << (1 << 10) << '\n'; // 2 的次方
cout << (n >> 1) << ' ' << (n >> 2) << '\n'; // 除以 2、除以 4
int arr[7] = {4, 7, 4, 9, 7, 3, 3};
int ans = 0;
for (int i = 0; i < 7; i++) {
ans = ans ^ arr[i]; // 成對的兩個會互相抵消
}
cout << ans << '\n'; // 只出現一次的那個數
return 0;
}
執行結果：
1 0
1 8 1024
12 6
9