Power Set Algorithm - Iterative

The power set of a set S is the set of all subsets of S including the empty set and S itself. For example, the power set of {1, 2, 3} is {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

Previously, I wrote about how you can generate the power set using a recursive algorithm. This time I'll show you how to use iteration.

Recall, that when we are generating a set for the power set, each element can either be in the set or out of the set. In other words, each set can be represented in binary form, where 1 means that the element is in the set and 0 means that it is not. For example, given a set {a, b, c}, the binary string 101 would represent {a, c}.

Generating the power set just comes down to generating all numbers from 0 to 2^n (since there are 2^n possible subsets) and converting the binary representation of the number into the set!

Here is the algorithm:

public static <E> List<List<E>> powerSet(final List<E> list) {
  final List<List<E>> result = new ArrayList<>();
  final int numSubSets = 1 << list.size(); // 2^n
  for (int i = 0; i < numSubSets; i++) {
    final List<E> subSet = new ArrayList<>();
    int index = 0;
    for (int j = i; j > 0; j >>= 1) { // keep shifting right
      if ((j & 1) == 1) { // check last bit
        subSet.add(list.get(index));
      }
      index++;
    }
    result.add(subSet);
  }
  return result;
}

Java Bit Twiddling

This post explains some of the less commonly used operators in Java, namely the bitwise and bit shift operators and how they can be cleverly used to multiply or divide integers, test for evenness etc. The operators are shown in the table below:

Name	Description
~a (NOT)	Negates each bit. 0s becomes 1s and vice versa. ~a=(-a)-1
a & b (AND)	In each pair of corresponding bits, the result is 1 if the first bit is 1 AND the second bit is 1, 0 otherwise.
a | b (OR)	In each pair of corresponding bits, the result is 1 if the first bit is 1 OR the second bit is 1 OR both bits are 1, and otherwise the result is 0
a ^ b (XOR)	In each pair of corresponding bits, the result in each position is 1 if the two bits are different, and 0 if they are the same.
a << n (LEFT-SHIFT)	Shifts bit pattern to the left by n positions and places 0s on the right.
a >> n (RIGHT-SHIFT)	Shifts bit pattern to the right by n positions and places the sign-bit on the left, thus preserving the sign of the operand.
a >>> n (UNSIGNED-RIGHT-SHIFT)	Shifts bit pattern to the right by n positions and places 0s on the left.

Examples of bitwise and bit shift operators in action:

a = 3 (11)
b = 6 (110)

~a = -4 (11111111111111111111111111111100)
a & b = 2 (10)
a | b = 7 (111)
a ^ b = 5 (101)
a << 2 = 12 (1100)
b >> 1 = 3 (11)
b >>> 1 = 3 (11)

The code used to generate this is shown below:

final int a = 3; // 011
final int b = 6; // 110

System.out.printf("a = %s\t(%s)\n", a,
                 Integer.toBinaryString(a));
System.out.printf("b = %s\t(%s)\n", b,
                 Integer.toBinaryString(b));

/**
 * NOT
 */
int not = ~a;
System.out.printf("~a = %s\t(%s)\n", not,
                 Integer.toBinaryString(not));

/**
 * AND
 */
int and = a & b;
// 011
// 110
//----&
// 010
System.out.printf("a & b = %s\t(%s)\n", and,
                 Integer.toBinaryString(and));

/**
 * OR
 */
int or = a | b ;
// 011
// 110
//----|
// 111
System.out.printf("a | b = %s\t(%s)\n", or,
                 Integer.toBinaryString(or));

/**
 * XOR
 */
int xor = a ^ b ;
// 011
// 110
//----^
// 101
System.out.printf("a ^ b = %s\t(%s)\n", xor,
                 Integer.toBinaryString(xor));

/**
 * LEFT-SHIFT
 */
int lshift = a << 2;
// 00011
// ----- <<2
// 01100
System.out.printf("a << 2 = %s\t(%s)\n", lshift,
                 Integer.toBinaryString(lshift));

/**
 * RIGHT-SHIFT
 */
int rshift = b >> 1;
// 110
// ----- >>1
// 011
System.out.printf("b >> 1 = %s\t(%s)\n", rshift,
                 Integer.toBinaryString(rshift));

/**
 * UNSIGNED-RIGHT-SHIFT
 */
int urshift = b >>> 1;
// 110
// ----- >>1
// 011
System.out.printf("b >>> 1 = %s\t(%s)\n", urshift,
                 Integer.toBinaryString(urshift));

Usage of bit manipulation:
So, where do you use this? In the olden days, they were used for efficiency but most modern compilers today perform optimisations for you, so you don't have to worry about it. The bitwise and bit shift operators are not used very frequently in day-to-day programming, but here are a few scenarios where they can be used - mainly to impress you colleagues :)

1. Checking if an integer is even or odd
If an integer is odd, its rightmost bit will always be 1 and if it is even, it will always be 0. For example, 4 is 100 and 5 is 101.

public boolean isEven(int a){
    return a & 1 == 0;
}

2. Multiplying/Dividing by powers of two
Shifting to the left is just like multiplying by a power of two. For example 3 << 2 is 12. In general, a << n is a*(2^n). Keep in mind that a left shift can result in "overflow" which occurs when you exceed the limits of the range of the data type you are using and can cause unexpected behaviour.

A right shift is an integer division by a power of 2. Shifting right 1 position is the same as dividing by two. This approach is used in the Collections Framework, such as the Arrays class to find the middle element of an array. In general, a >> n is a/(2^n). Be careful, when right shifting negative integers. For example, 5 >> 1 gives 2, but -5 >> 1, gives -3.

3. Is an integer positive or negative?
Shift the integer right 31 places. The value of the far left bit is copied to the other bits. The far left bit is 1 when the value is negative and 0 otherwise.

public boolean isNegative(int a){
    return (a >> 31) != 0;
}

4. Negating an integer
You can use the NOT operator to determine the negative of any integer as shown in the snippet below. The basic idea is you invert all the bits and then add 1.

int num = 4;
int neg = ~num + 1; //-4

Note that you can also do the reverse and determine the positive of a negative integer by subtracting 1 and then inverting the bits.

5. Check if the nth bit is set
This is a more generalised version of the even/odd check. We move the 1 bit n places to the left and then apply the AND operation. If the nth bit was not set, this would result in 0.

public boolean isBitSet(int a, int n){
    return a & (1 << n) != 0;
}

6. Setting the nth bit

a | (1<<n)

7. Unsetting the nth bit

a & ~(1<<n)

8. Toggling the nth bit

a ^ (1<<n)

9. Unsetting the rightmost 1-bit

a & (a-1)

10. Checking if number is a power of 2
If the number is a power of 2, there will be only one 1-bit. If we unset this bit, we will get 0.

return (a & (a-1)) == 0;

11. Swapping values without a temporary variable
Swap two variables without a temporary variable using XOR:

x = x ^ y;
y = x ^ y;
x = x ^ y;

References:
Bit Twiddling Hacks
Java Ranch - Bit Shifting
Low Level Bit Hacks You Absolutely Must Know