Menu
I'm trying to generate all possible combinations for pair of 1's within given bit width.
Let's say the bit width is 6, i.e. 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 that I'll loop over width - 1 times, and where I shift both a << 1 and b << 1, I'll get all combinations for one pair. After that, I'm pretty much stuck.
Could someone , please, provide some help.
Update: working example
Based on Barmar's mathematical approach, this is what 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/
610
asked Sep 05 '12 20:09
To fill a register with all 1 bits, on most machines the efficient way takes two instructions: Clear the register, using either a special-purpose clear instruction, or load immediate 0, or xor the register with itself. Take the bitwise complement of the register.
Each bit can be either 0 or 1, so you have two choices per bit. That gives you 2^n combinations.
It works by creating a "selection array" ( v ), where we place r selectors, then we create all permutations of these selectors, and print the corresponding set member if it is selected in in the current permutation of v . Hope this helps. This code is correct and it does produce combinations.
The numbers with exactly one pair of 1's are the sequence 3, 6, 12, 24, 48, ...; they start with 3 and just double each time.
The numbers with two pairs of 1's are 12+3, 24+3, 24+6, 48+3, 48+6, 48+12, ...; these are the above sequence starting at 12 + the original sequence up to n/4.
The numbers with three pairs of 1's are 48+12+3, 96+12+3, 96+24+3, 96+24+6, ...
The relationship between each of these suggests a recursive algorithm making use of the original doubling sequence. I don't have time right now to write it, but I think this should get you going.
144
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
