如何实现支持任意2的幂次n的通用逐位二进制增量器？

逐位二进制增量器是一种序列，每个后续状态仅通过修改前一个状态的一位得到，可遍历从0到2ⁿ-1的所有无重复二进制值（共2ⁿ个状态）。

示例代码（4位增量器） #

# Python
incrementer4 = (3, 2, 3, 1, 3, 2, 3, 0, 1, 3, 2, 3, 1, 3, 2)
pins = [0] * 4

def change(p, i):
    p[i] = 0 if p[i] else 1

print(pins)
for i in incrementer4:
    change(pins, i)
    print(pins)

通用实现方法 #

存在通用实现方案，这类序列本质是**格雷码（Gray Code）**对应的位翻转索引序列——格雷码的核心特性就是连续两个数值仅有一位不同，完全匹配增量器的需求。

实现思路 #

1. 生成格雷码序列：对每个整数i（从0到2ⁿ-1），对应的格雷码为 i ^ (i >> 1)（异或操作结合右移一位）。
2. 计算差异位索引：将连续两个格雷码做异或运算，结果中唯一为1的位就是需要翻转的引脚位置。
3. 索引适配示例格式：示例中采用高位引脚对应大索引的规则（如4位时最高位对应索引3），因此需将标准格雷码的低位索引转换为 n-1 - 原索引。

代码实现 #

def getIncrementer(n):
    # 生成n位格雷码列表
    gray_codes = [i ^ (i >> 1) for i in range(2 ** n)]
    incrementer = []
    for prev_gray, curr_gray in zip(gray_codes, gray_codes[1:]):
        # 计算相邻格雷码的差异位
        diff = prev_gray ^ curr_gray
        # 获取标准格雷码中的差异位索引（最低位为0）
        bit_pos = diff.bit_length() - 1
        # 转换为示例的高位优先索引规则
        incrementer.append(n - 1 - bit_pos)
    # 返回元组（与示例格式一致）
    return tuple(incrementer)

# 测试n=4，输出与示例一致
print(getIncrementer(4))
# 输出：(3, 2, 3, 1, 3, 2, 3, 0, 1, 3, 2, 3, 1, 3, 2)

说明 #

该方法对任意正整数n均有效（不限于2的幂），生成的序列能保证每次仅切换一个引脚，遍历所有2ⁿ个无重复状态，完全满足电子项目中优化读取时间的需求。

内容的提问来源于stack exchange，提问作者Alex Vergara