如何用NumPy高效生成所有n位格雷码？

我太懂你这种被库版本依赖折腾到崩溃的感受了——装了一堆库，每个都要抢不同版本的NumPy，更新一个就崩一片，干脆沉下心啃NumPy本身反而更踏实！你想要的是纯NumPy实现、最高效生成n位格雷码，输出形状为np.zeros((1 << n, n), dtype=bool)的布尔数组对吧？结合你自己做的大量测试和实现，我整理出最靠谱的高效方案，还有关键的性能优化思路。

先明确核心约束 #

• 纯NumPy实现，禁用其他任何库
• 输出必须是(2^n, n)的布尔数组
• 追求极致性能，优先内存连续、低复制的操作

高效实现方案 #

方案1：从二进制码快速转换（基于np.unpackbits） #

你自己测试发现np.unpackbits是生成二进制码最快的方式之一，我们可以基于这个快速生成二进制码，再转成格雷码——格雷码的核心规则是：最高位与二进制码相同，其余位为二进制当前位与前一位的异或。

先把你写的工具函数和核心实现整合：

import numpy as np

# 工具函数：获取对应位宽的无符号整数类型
UINT_BITS = {}
lo, hi = 1, 8
for dtype in (np.uint8, np.uint16, np.uint32, np.uint64):
    for i in range(lo, hi + 1):
        UINT_BITS[i] = dtype
    lo, hi = hi + 1, hi << 1

def get_dtype(n: int) -> np.dtype:
    if dtype := UINT_BITS.get(n):
        return dtype
    raise ValueError(f"Argument {n} is not a valid bit width")

def validate(n: int) -> None:
    if not (isinstance(n, int) and n > 0):
        raise ValueError(f"Argument {n} is not a valid positive integer bit width")

# 最快的二进制码生成（你测试的binary_codes_6）
def binary_codes_fast(n: int) -> np.ndarray:
    validate(n)
    return np.unpackbits(
        np.arange(1 << n, dtype=get_dtype(n))[:, None].view(np.uint8),
        axis=1,
        bitorder="little",
        count=n,
    )[:, ::-1].astype(bool)

# 基于二进制转格雷码的高效实现
def gray_codes_from_binary(n: int) -> np.ndarray:
    binary = binary_codes_fast(n)
    gray = binary.copy()
    # 从第二位开始，当前位 = 二进制当前位 ^ 二进制前一位
    gray[:, 1:] = binary[:, 1:] ^ binary[:, :-1]
    return gray

方案2：直接生成格雷码（递归拼接法） #

格雷码的经典生成规则是：n位格雷码可以由n-1位格雷码拼接得到——前半部分补0，后半部分倒序补1。这个方法避免了二进制转码的步骤，纯拼接操作：

def gray_codes_direct(n: int) -> np.ndarray:
    validate(n)
    # 初始化1位格雷码
    gray = np.array([[0], [1]], dtype=bool)
    current_length = 2
    for _ in range(n - 1):
        # 前半部分：补0 + 原格雷码
        part1 = np.concatenate([np.zeros((current_length, 1), dtype=bool), gray], axis=1)
        # 后半部分：补1 + 倒序的原格雷码
        part2 = np.concatenate([np.ones((current_length, 1), dtype=bool), gray[::-1]], axis=1)
        # 拼接得到新的格雷码
        gray = np.concatenate([part1, part2], axis=0)
        current_length <<= 1
    return gray

方案3：数值异或后拆分（你实现的gray_codes_0/1优化版） #

先生成0到2^n-1的整数，通过num ^ (num >> 1)得到格雷码数值，再拆分成布尔数组。这个方法利用NumPy的位运算，性能也很出色：

def gray_codes_bitwise(n: int) -> np.ndarray:
    validate(n)
    count = 1 << n
    # 生成所有数值，转格雷码
    nums = np.arange(count, dtype=get_dtype(n))
    gray_nums = nums ^ (nums >> 1)
    # 拆分每一位为布尔数组（循环赋值，内存更连续）
    result = np.zeros((count, n), dtype=bool)
    mask = count >> 1
    for i in range(n):
        result[:, i] = gray_nums & mask
        mask >>= 1
    return result

性能对比（基于你做的测试，n=16） #

你测试出的关键性能优化点（必须记牢！） #

这些都是你踩坑试出来的NumPy性能真经：

• 优先用np.concatenate替代hstack/vstack/dstack：尤其是指定axis参数的concatenate，底层更少的形状检查和内存复制，比如np.concatenate([a,b], axis=-1)比np.hstack([a,b])快10%以上；
• 广播操作要注意数组形状：(a & b[:, None]).T比(a[:, None] & b)快近30%，因为前者的内存访问更符合CPU缓存的连续读取规则；
• 循环赋值列有时比广播高效：比如binary_codes_5比binary_codes_4快，因为逐列赋值避免了大数组的广播开销，内存更紧凑；
• np.unpackbits是二进制生成的天花板：只要位宽不超过64，用unpackbits结合view转换类型，比任何手动拼接/广播都快，记得用bitorder="little"和count=n过滤多余位。

备注：内容来源于stack exchange，提问作者Ξένη Γήινος