What is the logic to use bitwise operation in generating subsequences?

Question

I have an array, A=[1,2,3,4] (where n=4). I want to generate sub-sequences from this array. Number of subsequences is (2^n -1)

Run from counter 0001 to 1111

for (int counter = 1; counter < 2^n; counter++)
{
    for (int j = 0; j < n; j++)
    {

Check if the jth bit in the counter is set. If set then print jth element from arr[]

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

can anyone explain me? How it works " counter & (1<

Please learn how to create a [Minimal, Complete, and Verifiable Example](http://stackoverflow.com/help/mcve). Don't split it up like you do. If you want to add comments, add them as source-code comments instead. — Some programmer dude, Jan 04 '18 at 15:16

jdehesa · Accepted Answer · 2018-01-05T10:05:36.910

The logic goes like this. Say, like you put in the example, you have n = 4, and, to avoid confusion, let's say the array is A = [5, 7, 8, 9], for example. Then you want all the possible sequences containing some elements (at least one) from the original array. So you want a sequence containing only the first one, a sequence containing the first and the second, the first and the third, etc. Each printed sequence may or may not contain each of the elements in the array. So you could see it as something like this:

| 5 | 7 | 8 | 9 |    Sequence
-----------------    --------
| 1 | 0 | 0 | 0 | -> 5
| 1 | 1 | 0 | 0 | -> 5 7
| 1 | 0 | 1 | 0 | -> 5 8
...

That is, each sequence can be expressed as a list of bits, each indicating whether each member of the array is included.

In this loop:

for (int counter = 1; counter < 2^n; counter++)

The program iterates from 1 to 2^n - 1, that is 15 in this case. So the values that you get for counter are:

Dec  Binary
---  ------
  1    0001
  2    0010
  3    0011
  4    0100
  5    0101
  6    0110
  7    0111
  8    1000
  9    1001
 10    1010
 11    1011
 12    1100
 13    1101
 14    1110
 15    1111

If you look closely, you will see that we have all the possible sequences of four elements composed of 0 and 1 in binary (except 0000, which would be the empty sequence and does not interest us). In this loop:

for (int j = 0; j < n; j++)

The program just goes through each bit of counter, from 0 (the rightmost) to n - 1 and whenever it finds a 1 it outputs the corresponding array element. The condition:

if (counter & (1<<j))

Simply computes the number 1<<j which is 1 plus j number of zeros at its right (so, for example, for j = 0 it would be 1 and for j = 2 it would be 100) and then a bitwise and operation, so it basically "filters" the j-th bit only (e.g. 1101 & 100 = 0100), and if the result is not zero then it means there was a one, and so arr[j] must be printed.

Obviously, the problem with the function is that it is limited to the number of bits that the variable counter can hold. That depends on its declared type and your architecture/compiler, but typically it will be either 32 or 64.

What is the logic to use bitwise operation in generating subsequences?

1 Answers1