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 2Expected 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?
(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 (<<)