How does bitwise & and << help in this subset problem?

user_18973963 0
Viewed 35

I am learning how to print all the subsets with same length in Javascript. And I saw this solution on w3resource.com:

JavaScript Function: Exercise-21 with Solution

Write a JavaScript function to get all possible subset with a fixed length (for example 2) combinations in an array.

Sample array : [1, 2, 3] and subset length is 2

Expected output : [[2, 1], [3, 1], [3, 2], [3, 2, 1]]

JavaScript Code:

function subset(arra, arra_size) {
    var result_set = [], 
        result;
    for(var x = 0; x < Math.pow(2, arra.length); x++) {
        result = [];
        i = arra.length - 1; 
        do {
            if( (x & (1 << i)) !== 0) {
                result.push(arra[i]);
            }
        }  while(i--);
        if( result.length >= arra_size) {
            result_set.push(result);
        }
    }

    return result_set; 
}

However I don't understand to logic behind the code especially the line with the bitwise operator. Could anyone explain please?

subset bit-manipulation arrays javascript
1 Answers

(x & (1 << i)) !== 0 means "does x have the ith bit set to 1?"

An example:

Let's say x in binary representation is 1001101

And let i go from 6 down to 0 (which is what the do loop does)

Then we get:

i 1 << i (binary) x & (1 << i) (binary)
6 1000000 1000000
5 100000 0
4 10000 0
3 1000 1000
2 100 100
1 10 0
0 1 1

The outer loop will produce all possible binary bit patterns with as many digits as there are values in the array.

This way, those bit patterns (x) actually describe all possible subsets of the array (a 1 bit means: include the corresponding array value, a 0 means: don't include it). The bit shift operator helps to isolate one bit in the bit pattern, so to decide whether or not to include the corresponding array value.

See MDN for the documentation on Bitwise AND (&) and Left shift (<<)

user_54598390
Related