Podzbiory

We are going to solve another simple task.

Here's the source: http://ki.staszic.waw.pl/task.php?name=podzbiory

And this is a rough translation:

Print all subsets of set A consisting of n elements. Note that each subset can be represented as a sequence of 0 and 1. If B is an array of booleans, B[i] shows whether element i is present in subset A or not.

For example: A = {2, 3, 5} can be represented as:
..................
B.=.{0, 1, 1, 0, 1}
........^..^.....^
........2..3.....5
The program reads one integer n = cardinality of A

For the following input:

3

The program is supposed to print:

000
001
010
011
100
101
110
111

How to solve it? We can easily see that the example explains more than the task itself. We are asked to simply print all numbers from 0 to 1 << n in binary form, where "<<" means Shift Left.

Let's solve the task using masks.

Let's consider the following integer:

011100110

How do we see if n-th bit of an integer is on or off? We simply multiply the integer with appropriate mask. We want to see if second bit (from the right) is on.

  11100110
* 00000010
__________
  00000010

If the answer != 0, the bit is on.

We now want to check whether the first bit is on.

  11100110
* 00000001
__________
  00000000

No, it isn't.

We can simply test it by calculating (i & (1<<j)) where i is the number we want to check and j is the bit we are interested of.

Solving the task with this knowledge is a piece of cake. We simply iterate through all numbers from 0 to 1 << n, and print the output in binary form.