C++ 二进制生成格雷码

在C++中生成二进制格雷码（Gray Code）可以通过几种不同的方法实现。格雷码是一种二进制数编码方式，其中两个连续的数只有一个比特位不同。以下是几种生成格雷码的方法及其详细实现：

方法1：直接生成

直接生成格雷码的公式是 G(i) = i ^ (i >> 1)，其中 G(i) 是第 i 个格雷码，^ 是按位异或操作，>> 是右移操作。

实现代码

cpp
复制代码
#include <iostream>
#include <vector>
#include <bitset>

std::vector<std::string> generateGrayCode(int n) {
    std::vector<std::string> result;
    int num_codes = 1 << n; // 2^n

    for (int i = 0; i < num_codes; ++i) {
        int gray = i ^ (i >> 1);
        result.push_back(std::bitset<32>(gray).to_string().substr(32 - n));
    }

    return result;
}

int main() {
    int n = 3; // Number of bits
    std::vector<std::string> gray_codes = generateGrayCode(n);

    for (const auto& code : gray_codes) {
        std::cout << code << std::endl;
    }

    return 0;
}

方法2：递归生成

递归生成格雷码是通过将小规模问题的解扩展为大规模问题的解来实现的。

实现代码

cpp
复制代码
#include <iostream>
#include <vector>
#include <string>

std::vector<std::string> generateGrayCode(int n) {
    if (n == 0) {
        return { "0" };
    }
    if (n == 1) {
        return { "0", "1" };
    }

    std::vector<std::string> previous_codes = generateGrayCode(n - 1);
    std::vector<std::string> result;

    // Append '0' to the first half
    for (const auto& code : previous_codes) {
        result.push_back("0" + code);
    }

    // Append '1' to the second half in reverse order
    for (auto it = previous_codes.rbegin(); it != previous_codes.rend(); ++it) {
        result.push_back("1" + *it);
    }

    return result;
}

int main() {
    int n = 3; // Number of bits
    std::vector<std::string> gray_codes = generateGrayCode(n);

    for (const auto& code : gray_codes) {
        std::cout << code << std::endl;
    }

    return 0;
}

方法3：迭代生成

迭代生成格雷码是通过逐次构建更大的格雷码序列来实现的。

实现代码

cpp
复制代码
#include <iostream>
#include <vector>
#include <string>

std::vector<std::string> generateGrayCode(int n) {
    std::vector<std::string> result = { "0", "1" };

    for (int i = 2; i <= n; ++i) {
        std::vector<std::string> new_result;

        // Append '0' to the first half
        for (const auto& code : result) {
            new_result.push_back("0" + code);
        }

        // Append '1' to the second half in reverse order
        for (auto it = result.rbegin(); it != result.rend(); ++it) {
            new_result.push_back("1" + *it);
        }

        result = new_result;
    }

    return result;
}

int main() {
    int n = 3; // Number of bits
    std::vector<std::string> gray_codes = generateGrayCode(n);

    for (const auto& code : gray_codes) {
        std::cout << code << std::endl;
    }

    return 0;
}

总结

以上三种方法展示了如何在C++中生成二进制格雷码。方法1使用直接生成的公式，方法2使用递归生成，方法3使用迭代生成。每种方法都有其优点，选择哪种方法取决于具体需求和偏好。

关键字

C++，二进制，格雷码，Gray Code，直接生成，递归生成，迭代生成，异或，位操作。