Time Complexity:
Here is an alternative way to derive the time complexity (compared to @templatetypedef).
Let M be the total number of steps in the code. Your outer for-loop runs 2N times and the inner one runs log(i) times so we have:
Raise 2 to each side of the above equation and simplify:
Take the log of both sides of the above equation, and use Sterlings Approximation (Log(x!) ~ xLog(x) - x)
Bit Operations:
To address your weakness in bit manipulation you actually don't need it. It's used in three ways in your code, all of which can be replaced with less obfuscated functions:
- Power of 2: (
1 << array.length
) → (Math.pow(2, array.length)
) - Divide by 2: (
x >>= 1
) → (x /= 2
) - modulus 2:
(x & 1)
→(x % 2)
Code Explaination:
Also, to address the what the code is doing, it's essentially converting each number (0 to 2N) into it's binary form using the method shown here, and as @templatetypedef states, 1 means that corresponding element is in the set. Here is an example of converting 156 to binary with this method:
As an example with your code:
pos = array.length - 1;
bitmask = 156; // as an example, take bitmask = 156
while(bitmask > 0){
if(bitmask%2 == 1) // odd == remainder 1, it is in the set
System.out.print(array[pos]+",");
bitmask /= 2; // divide by 2
pos--;
}
By doing this for all bitmasks (0 to 2N) you are finding all unique possible sets.
EDIT:
Here is a look at the ratio (n2n/log2(2n!) in sterling approximation you can see that it quickly approaches unity as n gets large: