Generieren Sie alle Kombinationen für ein Bitpaar, das auf 1 gesetzt ist?

Question

Ich versuche, alle möglichen Kombinationen für ein Paar von 1 innerhalb einer gegebenen Bitbreite zu generieren.

Nehmen wir an, die Bitbreite 6, dh die Zahl 32. Dies ist, was ich möchte generieren:

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

Wenn ich Variablen:

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

und eine Schleife erstellen, die ich Schleife über width - 1 mal, und wo ich sowohl a << 1 und b << 1 verschiebe, werde ich alle Kombinationen für ein Paar bekommen. Danach stecke ich ziemlich fest.

Könnte jemand bitte Hilfe leisten.

Update: Arbeitsbeispiel
Basierend auf Barmar mathematischen Ansatz, ist das, was ich

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

Arbeitsbeispiel auf JSFiddle
http://jsfiddle.net/zywc5/

Answer 1

Die Zahlen mit genau einem Paar von 1en sind die Reihenfolge 3, 6, 12, 24, 48, ...; Sie beginnen mit 3 und sind jeweils doppelt so groß.

Die Zahlen mit zwei Paaren von 1 sind 12 + 3, 24 + 3, 24 + 6, 48 + 3, 48 + 6, 48 + 12, ...; dies ist die obige Sequenz beginnend bei 12 + der ursprünglichen Sequenz bis zu n/4.

Die Zahlen mit drei Paaren von 1en sind 48 + 12 + 3, 96 + 12 + 3, 96 + 24 + 3, 96 + 24 + 6, ...

Die Beziehung zwischen jedem dieser schlägt ein rekursiver Algorithmus, der die ursprüngliche Verdopplungssequenz verwendet. Ich habe momentan keine Zeit, es zu schreiben, aber ich denke, das sollte dich weiterbringen.

Answer 2

wenn die Bitbreite isn implementieren verwaltet Wenn du so groß bist, bist du viel besser dran, Bit-Repräsentationen für alle Zahlen von 0 bis 31 in einer Schleife zu erstellen und ignorierst einfach th diejenigen, die eine ungerade Anzahl von "Einsen" in der Bit-Darstellung haben.

Answer 3

Vielleicht beginnen normalerweise in binären Zählen und ersetzen alle 1 mit 11 ist wie folgt aus:

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

So erhalten Sie:

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

Und so weiter. Sie müssen auf der linken Seite bis zu 31 Punkte zählen und auf der rechten Seite länger als 6 Bit zurückweisen.

Answer 4

Siehe 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 />')); 

Oder vielleicht werden Sie http://jsfiddle.net/SBH6R/1/ bevorzugen. Es ist einfacher, aber dann werden Sie sort() das Array haben:

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 Sehen Sie, wenn Sie die Leistung vergleichen möchten.Es scheint, dass der schnellste Code der erste in Chrome ist, aber der zweite in Firefox.

Answer 5

Sie können auch mit wenig twiddling tun. Wenn die niedrigsten zwei Bits Null sind, müssen wir sie setzen, was dem Addieren von 3 entspricht. Ansonsten müssen wir den untersten Block von Einsen durch sein oberes Bit und ein 1-Bit links davon ersetzen. Dies kann wie folgt geschehen, wobei x die aktuelle Kombination ist:

x3 = x + 3; 
return (((x^x3) - 2) >> 2) + x3;