6

指定されたビット幅内で 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、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/での作業例

4

5 に答える 5

3

1のペアが1つだけの番号は、シーケンス3、6、12、24、48、...です。それらは3から始まり、毎回2倍になります。

1のペアが2つある数字は、12 + 3、24 + 3、24 + 6、48 + 3、48 + 6、48 + 12、...; これらは、12+元のシーケンスからn/4までの上記のシーケンスです。

1の3つのペアを持つ数字は、48 + 12 + 3、96 + 12 + 3、96 + 24 + 3、96 + 24 + 6、..です。

これらのそれぞれの間の関係は、元のダブリングシーケンスを利用する再帰的アルゴリズムを示唆しています。今は書く時間がありませんが、これでうまくいくと思います。

于 2012-09-05T20:54:51.713 に答える
0

たぶん、通常は2進数でカウントを開始し、次のようにすべての1を11に置き換えます。

n = 5
n = n.toString(2)          //= "101"
n = n.replace(/1/g, "11")  //= "11011"
n = parseInt(n, 2)         //= 27

だからあなたは得るでしょう：

0   -> 0
1   -> 11
10  -> 110
11  -> 1111
100 -> 1100
101 -> 11011
110 -> 11110
111 -> 111111

等々。左側で最大31程度をカウントし、右側で6ビットより長いものを拒否する必要があります。

于 2012-09-05T20:53:16.873 に答える
0

ビット幅がそれほど大きくない場合は、ループ内の0から31までのすべての数値のビット表現を作成し、ビット表現に奇数の「1」があるものを単に無視する方がはるかに良いでしょう。

于 2012-09-05T20:44:14.200 に答える
0

http://jsfiddle.net/SBH6R/を参照してください

var len=6,
    arr=[''];
for(var i=0;i<len;i++){
    for(var j=0;j<arr.length;j++){
        var k=j;
        if(getNum1(arr[j])%2===1){
            arr[j]+=1;
        }else{
            if(i<len-1){
                arr.splice(j+1,0,arr[j]+1);
                j++;
            }
            arr[k]+=0;
        }      
    }
}
function getNum1(str){
    var n=0;
    for(var i=str.length-1;i>=0;i--){
        if(str.substr(i,1)==='1'){n++;}
        else{break;}
    }
    return n;
}
document.write(arr.join('<br />'));

または、 http://jsfiddle.net/SBH6R/1/を好むかもしれません。より簡単ですがsort()、配列を作成する必要があります。

var len=6,
    arr=[''];
for(var i=0;i<len;i++){
    for(var k=0,l=arr.length;k<l;k++){
        if(getNum1(arr[k])%2===1){
            arr[k]+=1;
        }else{
            if(i<len-1){
                arr.push(arr[k]+1);
            }
            arr[k]+=0;
        }     
    }
}
function getNum1(str){
    var n=0;
    for(var i=str.length-1;i>=0;i--){
        if(str.substr(i,1)==='1'){n++;}
        else{break;}
    }
    return n;
}
document.write(arr.sort().join('<br />'));

パフォーマンスを比較したい場合は、http://jsperf.com/generate-all-combinations-for-pair-of-bits-set-to-1を参照してください。最速のコードは、Chrome では最初のコードですが、Firefox では 2 番目のコードのようです。

于 2012-09-05T22:00:47.167 に答える