Generate all combinations for a pair of bits set to 1?

Question

I am trying to create all possible combinations for pair 1 within a given width.

Let's say the bit width is 6, that is, number 32. This is what I would like to generate:

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

If I have variables:

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

and create a loop in which I will cyclically switch to width - 1 time, and when I shift both a << 1 and b << 1 , I will get all the combinations for one pair. After that, I got pretty stuck.

Can someone please provide some help.

Update: working example
Based on Barmar's mathematical approach, I managed to implement

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

Working example on JSFiddle
http://jsfiddle.net/zywc5/

Answer 1

Numbers with exactly one pair 1 are the sequence 3, 6, 12, 24, 48, ...; they start at 3 and just double each time.

Numbers with two pairs 1 are 12 + 3, 24 + 3, 24 + 6, 48 + 3, 48 + 6, 48 + 12, ...; this is the above sequence starting from 12 + the original sequence to n / 4.

Numbers with three pairs of 1 are 48 + 12 + 3, 96 + 12 + 3, 96 + 24 + 3, 96 + 24 + 6, ...

The relationship between each of them involves a recursive algorithm using the original doubling sequence. I don’t have time to write it, but I think it should make you go.

Answer 2

if the bit width is not so large, you would be better off creating bit representations for all numbers from 0 to 31 in the loop and just ignore those that have an odd number of “units” in the bit representation.

Answer 3

Perhaps start usually counting in binary format and replace all 1 with 11 as follows:

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

So you get:

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

Etc. You will need to count to 31 or so on the left side and reject more than 6 bits on the right side.

Answer 4

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

Or maybe you would prefer http://jsfiddle.net/SBH6R/1/ . This is simpler, but then you need a sort() array:

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

See http://jsperf.com/generate-all-combinations-for-pair-of-bits-set-to-1 if you want to compare performance. It seems that the fastest code is the first in Chrome and the second in Firefox.

Answer 5

You can also do this with bit twisting. If the lower two bits are zero, we need to set them, which is equivalent to adding 3. Otherwise, we need to replace the lowest block with its upper bit and 1-bit to the left of it. This can be done as follows, where x is the current combination:

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