格雷码

题目解析

给定 n 和 k，输出 n 位格雷码的第 k 个编码（k 从 0 开始编号）。

格雷码的性质：相邻两个编码只有一位不同，且具有镜像对称性质。

求解思路

格雷码有经典构造公式：

g(k) = k \oplus \left\lfloor \frac{k}{2} \right\rfloor

即 k ^ (k >> 1)，对应二进制就是 n 位格雷码中的第 k 个编码。

验证：

n=2, k=3 → 3 ^ 1 = 2 → 10 ✓
n=3, k=5 → 5 ^ 2 = 7 → 111 ✓

1.cpp 做法 (位运算递推)

代码采用另一种按位递推的思路，从低位向高位逐位确定：

对于第 i 位（i 从 1 开始，对应 $2^i$ 分组），块大小 $t = 2^i$
计算块编号 $t2 = k / t$ 和块内偏移 $t3 = k \% t$
若块编号为奇数，则块内前一半输出 1，后一半输出 0；偶数则相反

这样递推得到每一位，等价于格雷码公式的展开形式。

计算示例

例 1： n=2, k=3

i	t = 2ⁱ	t2 = k/t	t3 = k%t	t/2	t2 奇偶	条件 t3 < t/2	a[i]
1	2	3/2=1	3%2=1	1	奇	1<1? 否 → 0	0
2	4	3/4=0	3%4=3	2	偶	3<2? 否 → 1	1

a[1]=0, a[2]=1 → 倒序输出 10 ✓

例 2： n=3, k=5

i	t = 2ⁱ	t2 = k/t	t3 = k%t	t/2	t2 奇偶	条件 t3 < t/2	a[i]
1	2	5/2=2	5%2=1	1	偶	1<1? 否 → 1	1
2	4	5/4=1	5%4=1	2	奇	1<2? 是 → 1	1
3	8	5/8=0	5%8=5	4	偶	5<4? 否 → 1	1

a[1]=1, a[2]=1, a[3]=1 → 倒序输出 111 ✓

注意

n 最大为 64，k 可达 $2^{64}$ ，需要用 __int128 或 unsigned long long 处理。

代码

cpp

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

using std::cin;
using std::cout;

std::size_t n,k;
__int128 n1,k1;
int a[100];//存答案
int main (int argc, char *argv[]) {
    std::cin >> n >> k;
    n1 = n;
    k1 = k;
    for(int i =1; i<=n;i++) {
        __int128 t = 1;
        t <<= i;
        __int128 t2 = k1 / t;
        __int128 t3 = k1 % t;
        if( t2 & 1) { //奇数
            if( t3 < t/2 )
                a[i] = 1;
            else
                a[i] = 0;
        }
        else  //偶数
        {
            if( t3 < t/2 )
                a[i] = 0;
            else
                a[i] = 1;
        }
    }

    for(int i = 1;i <= n ;++i ) // i: 1->n
    {
        cout << a[n-i+1];
    }
    return 0;
}

目录

题目解析

求解思路

1.cpp 做法 (位运算递推)

计算示例

注意

代码