在没有偏见的情况下计算一系列数字的最有效方法？

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;
}