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;
}
}
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
.