I've been looking at algorithms that list all the possible combinations of an array of boolean values.

For example, an array of two booleans can have these combinations: [true, true], [true, false], [false, true], [false, false]

I've found several examples that use bitwise operators and whilst I've looked up the definitions of the operators used, I still don't understand their contextual use in the algorithms.

I've listed an example algorithm (source: http://zacg.github.io/blog/2013/08/02/binary-combinations-in-javascript/) below with annotations to describe what I'm seeing when I look at them:

function binaryCombos(n){
    var result = [];
    for(y=0; y<Math.pow(2,n); y  ){         // This cycles through the maximum number of combinations 
                                               (power of 2 because it's binary)
        
    var combo = [];                         // combo for particular iteration, eventually pushed to result
        for(x=0; x<n; x  ){                 // iterate over number of booleans in array
            //shift bit and and it with 1
            if((y >> x) & 1)                // right shifts and then masks for 1? i.e. tests if it's odd??
                combo.push(true);           // I don't see how this ensures all combiantions are covered
             else 
                combo.push(false);          // I don't understand the criteria for pushing false or true :(        
        }
        result.push(combo);
    }
    return result;
}

//Usage
combos = binaryCombos(3);


for(x=0; x<combos.length; x  ){               // This looks like driver code so have been ignoring this
    console.log(combos[x].join(','));
}

Here's an example working with n = 2:

y = 0 x = 0

0 >> 0 is still 0 so will evaluate to false when 'anded' with 1 as:

0000 0000 & 0000 0001 --> 0

'false' pushed to combo array

y=0 x=1

0 >> 1 still 0 and will push 'false' to combo array

pushed to results: [false, false]

y=1 x=0

1 >> 0 equates to 0000 0001 with no shift(?) so 'anding' with 1 will evaluate to true, 'true' pushed to combo array

y=1 x=1

1 >> 1 is the same as halving but would eval to 0 so false is pushed to combo array

pushed to results: [true, false]

y=2 x=0

2 >> 0 equates to false being pushed to combo array as 0000 0010 & 0000 0001 = 0

y=2 x=1

2 >> 1 equates to true being pushed as 0000 0001 & 0000 0001 = 1

pushed to results: [false, true]

y=3 x=0

3 >> 0 equates to true being pushed to combo array since 0000 0011 & 0000 0001 = 1

y=3 x=1

3 >> 1 equates to true being pushed to combo array

pushed to results: [true, true]

result returned: [[false, false], [true, false], [false, true], [true, true]]

I can intuitively see that nested loops will help solve permutations and I can recognize that this has arrived at the correct answer but can't see the relationship between shifting y by x and then 'anding' with comprehensively covering all combinations.

Any help appreciated!

CodePudding user response：

x is a (zero-based) bit number. That bit number refers to a bit in the binary representation of y: the least significant bit has number 0 (at the right of the binary representation), and the most significant bit has number n-1. As a combination has n boolean values, the bit representation (of y) has n bits. A zero-bit translates to false and a 1-bit to true.

Now, to extract the x^th bit from the binary representation of y, we can use the shift operator:

y >> x

After this operation, the bit we are interested in has moved all the way to the right. All the bits that were at the right of the x^th bit have "fallen of" by this >> operation. What remains is to get rid of all the bits at the left of the bit we want to extract. For that we use & 1. That's all that is needed to isolate the x^th bit of the binary representation of y.

Example

Let's say we have n=4 and the outer loop has iterated to the point where y=13. The binary representation of y is 1101.

The loop on x will start with x=0, so the shift operation will not do anything, but the & 1 operation will extract the right-most bit of 1101, i.e. 1.

The next inner iteration will have x=1. Now the shift operation will kick that right most bit out, and we are left with 110. The & 1 operation will now extract the 0. And so it continues for x=3 and x=4.

Here represented in a table (for n=4 and y=13):