題意#
給定一個整數 \( n \)，要求構造出長度為 \( n \) 的「格雷碼（Gray Code）」序列。
格雷碼序列必須包含所有 \( 2^n \) 種二進位字串，
此數列的相鄰二進位字串之間，只能剛好有一個位元是不同的。
思路#
此題可以透過字串拼接加遞迴來推導，
但我們也可以透過位元運算公式，將十進位數字直接轉換為對應的格雷碼。
轉換公式為：將數字本身與「數字往右位移 1 位」的結果進行 XOR 運算，也就是 i ^ (i >> 1)。
這個結果恰好會是第 \( i \) 個格雷碼的十進位數值。
因此我們只要開一個迴圈，從 0 遍歷到 \( 2^n - 1 \)，
計算出格雷碼十進位數值後，再將其轉回 0 和 1 的二進位字串。
實作上要注意，轉換二進位時低位元會先出現，所以需要將字串反轉。
此外，數字高位欠缺的 0 也需補齊（長度不夠 \( n \) 的部分要在左側補 0）。
例如在 C++ 裡可搭配 setw(n) 和 setfill('0') 輸出，即可補齊長度。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
signed main() { WA();
int n;
cin >> n; // 讀取要求的格雷碼長度 n
// 總共跑 2^n 種所有排列組合的窮舉迴圈
for (int i = 0; i < (1<<n); i++) {
string s;
// 位元轉換公式：利用 i^(i>>1) 神奇地直接算出第 i 個格雷碼數值
// 將這些位元轉換成我們熟悉的 0、1 字串形式 (反轉方向寫入)
for (int j = i^(i>>1); j; j>>=1) s += (j&1)+'0';
// 字串反轉回正確的讀取順序，加上 setfill 和 setw 在左側強行補 0 湊齊長度 n
cout << setfill('0') << setw(n) << string(s.rbegin(), s.rend()) << '\n';
}
}
