What does the statement if (counter & (1<<j)) mean and how does it work?

Question

I was working on an algorithm of sub sequences.

What is the meaning of the statement:

if (counter & (1<<j))

within the context of the program below:

void printSubsequences(int arr[], int n)
{
    unsigned int opsize = pow(2, n);

    for (int counter = 1; counter < opsize; counter++)
    {
        for (int j = 0; j < n; j++)
        {
            if (counter & (1<<j))
                cout << arr[j] << " ";
        }
        cout << endl;
    }
}

Solution

The statement:

if (counter & (1<<j))

checks if the j-th bit of counter is set. In more detail, 1 << j uses shifting of 1 to generate a bit mask in which only the j-th bit is set. The & operator then masks out the j-bit of counter; if the result is not zero (which means that the j-th bit of counter was set), the condition is satisfied.

Consider the following example. If counter is 320, its binary representation is 101000000, which means that the 6th bit (the one corresponding to the value of 64) is set; let's test for that bit. The bit mask is generated by shifting 1, which has the binary representation 000000001, 6 places to the right, which results in the binary value 001000000. The value of counter, namely:

101000000

is combined with &, which is the bitwise and-operator, with the bit mask as follows:

  101000000
& 001000000
  ---------
  001000000

The value 001000000 again corresponds to the value of 64; however this is not important here, it only matters that it is not zero (as it has a nonzero bit, namely the bit for which we intended to check). In total, the condition

if ( 64 )

is satisfied. In the semantics of C (which does not feature a native Boolean data type) any nonzero value is treated as true when checked with if.

Comments

[Sarathi Shah]

can you please give me step by step execution of it?

[shinzou]

The first loop generates all possible combinations and the second loop print according to those combinations. @SarathiShah

[varungupta]

The operation x<<y basically means ' Perform Left shift on binary(x) by y number of bits ' So 6<<2 will give out 24 SINCE --------> lshift(110) by 2 bits -----> 11000 = 24 in decimal.