c - 无偏见地计算一系列数字的最有效方法？

Question

我想将一系列数字打印到 STDOUT。但不是从 0、1、2 ... N-1、N 开始计数，我想使用广度优先搜索进行迭代。我想用尽可能少/最不密集的指令来做到这一点(即没有分支)。

例如，假设范围是 [1, 128]。我想这样数:

64
32
96
16
87
...
128
1

坦率地说，我不在乎是广度优先还是深度优先，或者其他什么。我只想要一个均匀覆盖数字线的计数算法，这样如果数字线是一个跷跷板，它会从算法的开始到结束都是平衡的。

不，这不是家庭作业:-P

编辑:寻找复杂度为 O(n) 且不依赖于存储整个列表的东西。

Answer 1

使用反转位作为键对数字进行排序。

这段 Python 代码演示了这个概念:

>>> sorted(range(1,128), key=lambda x: ('{:08b}'.format(x))[::-1])
[64, 32, 96, 16, 80, 48, 112, 8, 72, 40, 104, 24, 88, 56, 120, 4, 68, 36, 100, 20, 84, 52, 116, 12, 76, 44, 108, 28, 92, 60, 124, 2, 66, 34, 98, 18, 82, 50, 114, 10, 74, 42, 106, 26, 90, 58, 122, 6, 70, 38, 102, 22, 86, 54, 118, 14, 78, 46, 110, 30, 94, 62, 126, 1, 65, 33, 97, 17, 81, 49, 113, 9, 73, 41, 105, 25, 89, 57, 121, 5, 69, 37, 101, 21, 85, 53, 117, 13, 77, 45, 109, 29, 93, 61, 125, 3, 67, 35, 99, 19, 83, 51, 115, 11, 75, 43, 107, 27, 91, 59, 123, 7, 71, 39, 103, 23, 87, 55, 119, 15, 79, 47, 111, 31, 95, 63, 127]

查看每个数字的位模式可以了解其工作原理/原因:

>>> '{:08b}'.format(64)
'01000000'
>>> '{:08b}'.format(32)
'00100000'
>>> '{:08b}'.format(96)
'01100000'

注意，这个过程也可以即时完成，不需要排序:

>>> [int('{:07b}'.format(i)[::-1], 2) for i in range(1, 128)]
[64, 32, 96, 16, 80, 48, 112, 8, 72, 40, 104, 24, 88, 56, 120, 4, 68, 36, 100, 20, 84, 52, 116, 12, 76, 44, 108, 28, 92, 60, 124, 2, 66, 34, 98, 18, 82, 50, 114, 10, 74, 42, 106, 26, 90, 58, 122, 6, 70, 38, 102, 22, 86, 54, 118, 14, 78, 46, 110, 30, 94, 62, 126, 1, 65, 33, 97, 17, 81, 49, 113, 9, 73, 41, 105, 25, 89, 57, 121, 5, 69, 37, 101, 21, 85, 53, 117, 13, 77, 45, 109, 29, 93, 61, 125, 3, 67, 35, 99, 19, 83, 51, 115, 11, 75, 43, 107, 27, 91, 59, 123, 7, 71, 39, 103, 23, 87, 55, 119, 15, 79, 47, 111, 31, 95, 63, 127]

在 C 中，反转位是一个微不足道的练习:

long reverse(long x) {
    long result = 0:
    int i;

    for (i=0 ; i<32 ; i++) {
        result <<= 1;
        result |= x & 1;
        x >>= 1;
    }
    return result;
}