Wygeneruj wszystkie kombinacje dla pary bitów ustawionej na 1?

Question

Próbuję wygenerować wszystkie możliwe kombinacje dla pary 1 w ramach danej szerokości bitowej.

Powiedzmy szerokość bit jest 6, czyli numer 32. To jest to, co chciałbym wygenerować:

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

Jeśli mam zmienne:

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

i stworzyć pętlę, że Pętla nad width - 1 razy, i gdzie przestawię oba a << 1 i b << 1, otrzymam wszystkie kombinacje dla jednej pary. Po tym jestem prawie utknął.

Czy ktoś mógłby, proszę, udzielić pomocy.

Aktualizacja: przykład pracy
podstawie matematycznego podejścia Barmar, jest to, co udało mi się wdrożyć

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

przykład roboczych na JSFiddle
http://jsfiddle.net/zywc5/

Answer 1

Liczby z dokładnie jedną parą 1-sza to sekwencja 3, 6, 12, 24, 48, ...; zaczynają się od 3 i po prostu dwukrotnie za każdym razem.

Liczby z dwiema parami 1 to 12 + 3, 24 + 3, 24 + 6, 48 + 3, 48 + 6, 48 + 12, ...; są to powyższa sekwencja zaczynająca się od 12 + pierwotna sekwencja do n/4.

Numery z trzech par 1 są 48 + 12 + 3 96 + 3 + 12 96 + 24 + 3 96 + 6 24 + ...

Związek pomiędzy każdą z nich sugeruje rekursywny algorytm wykorzystujący oryginalną sekwencję podwojenia. Nie mam teraz czasu, aby to napisać, ale myślę, że to powinno cię skłonić.

Answer 2

jeśli nieco szerokość ISN W takim razie lepiej będzie, jeśli stworzysz bitowe reprezentacje dla wszystkich liczb od 0 do 31 w pętli i po prostu zignoruj Te, które mają nieparzystą liczbę "jedynek" w reprezentacji bitów.

Answer 3

Może rozpocząć liczenie zwykle w binarnym i zastąpić wszystkie 1 jest z 11 jest tak:

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

Więc dostaniesz:

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

i tak dalej. Musisz liczyć do 31 lub mniej po lewej stronie i odrzucić dłuższe niż 6 bitów po prawej stronie.

Answer 4

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

Albo będzie wolisz http://jsfiddle.net/SBH6R/1/. To prostsze, ale wtedy trzeba będzie sort() tablicę:

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

Zobacz http://jsperf.com/generate-all-combinations-for-pair-of-bits-set-to-1 jeśli chcesz porównać skuteczność.Wygląda na to, że najszybszy kod jest pierwszym w Chrome, a drugi w Firefoksie.

Answer 5

Można to również zrobić za pomocą twiddlingu bitowego. Jeśli najniższe dwa bity są zerowe, musimy je ustawić, co jest równoznaczne z dodaniem 3. W przeciwnym razie musimy zastąpić najniższy blok przez swój górny bit i 1-bitowy na lewo od niego. Można to zrobić w następujący sposób, gdzie x jest aktualną kombinacją:

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