生成设置为1的位对的所有组合？

Question

我试图在给定的位宽内生成1对1的所有可能组合.

假设位宽为6,即数字32.这就是我想要生成的:

000000
000011
000110
001100
001111
011000
011011
011110
110000
110011
110110
111100
111111

如果我有变量:

var a = 1,
    b = 2;
    num = a | b;

并创建一个循环,我会遍历width - 1次,在那里我既转移a << 1和b << 1,我会得到所有的组合为一对.在那之后,我几乎陷入困境.

有人可以提供一些帮助.

更新:工作示例
基于Barmar的数学方法,这是我设法实现的

var arr = [],
    arrBits = [];

function getCombs(pairs, startIdx) {
    var i, j, val = 0, tmpVal, idx;

    if (startIdx + 2 < pairs) {
        startIdx = arr.length - 1;
        pairs -= 1;
    }

    if (pairs < 2) {
        return;
    }

    for (i = 0; i < pairs-1; i++) {
        idx = startIdx - (i * 2);
        val += arr[idx];

    }

    for (j = 0; j < idx - 1; j++) {
        arrBits.push((val + arr[j]).toString(2));
    }

    getCombs(pairs, startIdx-1);
}

(function initArr(bits) {
    var i, val, pairs, startIdx;

    for (i = 1; i < bits; i++) {
        val = i == 1 ? 3 : val * 2;
        arr.push(val);
        arrBits.push(val.toString(2));
    }

    pairs = Math.floor(bits / 2);
    startIdx = arr.length - 1;

    getCombs(pairs, startIdx);
    console.log(arrBits);

}(9));

关于JSFiddle的工作示例
http://jsfiddle.net/zywc5/

Answer 1

正好有一对 1 的数字是序列 3, 6, 12, 24, 48, ...；他们从 3 开始，每次都加倍。

含有两对 1 的数字是 12+3、24+3、24+6、48+3、48+6、48+12、...；这些是上面的序列，从 12 开始 + 原始序列到 n/4。

含有三对 1 的数字是 48+12+3、96+12+3、96+24+3、96+24+6、...

这些之间的关系表明了一种利用原始加倍序列的递归算法。我现在没有时间写它，但我想这应该能让你继续下去。