-4
void printPowerSet(char *set, int set_size) {

  unsigned int pow_set_size = pow(2, set_size);
  int counter, j;

  for (counter = 0; counter < pow_set_size; counter++) {
    for (j = 0; j < set_size; j++) {

      if (counter & (1 << j))
        cout << set[j];
    }
    cout << endl;
  }
}

I am not able to understand the if (counter & (1 << j)) part here. How can this code give subsets of a set {a,b,c}?

brc-dd
  • 10,788
  • 3
  • 47
  • 67
Manav Popli
  • 1
  • Does this answer your question? [Why is bitwise operator needed in this powerset generator?](https://stackoverflow.com/questions/57948316/why-is-bitwise-operator-needed-in-this-powerset-generator) PS : `x & 1` is basically a way of checking `x % 2 == 1`, i.e. if `x` is odd. Here you're shifting it, so it is checking if `j`th bit from right is set or not. – brc-dd Aug 29 '20 at 08:29

1 Answers1

0

The main loop is iterating from 0 to (2^set_size)-1. For example if there are three elements in the set it will iterate from 0 to 7 ((2^3)-1). If you represent it in binary it will be: 000, 001, 010, 011, 100, 101, 110, 111. These are all subsets of a three-element set (1 - we take the element, 0 - we don't take it). Now you only need to iterate and check if we take j-th element (if the j-th bit is equal to 1). The easiest way to do it is to check if (i & (2^j)) is equal to a non-zero value (& is a bitwise operation that for every position in the numbers returns 1 if in both numbers have on this position a lit bit and 0 in any other case). The if operation treats 0 as false and positive values as true, so if the j-th bit is lit the operation will return 2^j and it will be a true value, so this element will be taken to this subset, otherwise if the bit isn't lit the operation will return 0, so this element isn't in this subset .

Zuzanna Ossowska
  • 1
  • 2