Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

if (counter & (1<<j)) .what does this statement mean and how it works? [duplicate]

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;
    }
}
like image 760
Sarathi Shah Avatar asked Jan 13 '17 07:01

Sarathi Shah


1 Answers

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.

like image 52
Codor Avatar answered Sep 21 '22 19:09

Codor