如何高效以二进制形式生成前N个自然数的元组表示？

需求说明 #

给定正整数N，需按顺序生成0到N-1（从0开始的自然数）的二进制表示，所有结果以元组形式呈现，且需补前导零使所有元组长度一致。要求算法完全在二进制域操作，禁止使用bin()、f'{n:b}'等进制转换相关函数，避免冗余计算。

已实现的纯二进制域生成器 #

本人已实现符合要求的纯Python生成器函数：

from typing import Generator, Tuple

def count_in_binary(n: int) -> Generator[Tuple[int, ...], None, None]:
    if not isinstance(n, int) or n < 1:
        raise ValueError("The argument n must be a positive integer")

    l = (n - 1).bit_length() if n > 1 else 1
    numeral = [0] * l
    maxi = l - 1
    for _ in range(n):
        yield tuple(numeral)
        i = maxi
        while True:
            if not (d := numeral[i]):
                numeral[i] = 1
                break
            else:
                numeral[i] = 0
                i -= 1

对比实现（效率更低） #

以下是使用进制转换函数的实现，虽简洁但效率更低：

def count_in_binary1(n: int) -> Generator[Tuple[int, ...], None, None]:
    if not isinstance(n, int) or n < 1:
        raise ValueError("The argument n must be a positive integer")

    l = len(f'{n-1:b}')
    for i in range(n):
        yield tuple(map(int, f'{i:0{l}b}'))

性能测试结果 #

In [50]: %timeit list(count_in_binary(256))
59.9 μs ± 209 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

In [51]: %timeit list(count_in_binary1(256))
452 μs ± 3.68 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

补充说明 #

• 仅允许纯Python实现，禁止使用NumPy
• 原函数已修复问题，目前无异常
• 相关问题已在Stack Overflow发布新帖

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