17

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;
    }
}
phuclv
  • 37,963
  • 15
  • 156
  • 475
Sarathi Shah
  • 305
  • 1
  • 2
  • 8
  • 3
    `<<` means that the left-hand operand is multiplied by 2, for as many times as the number in the right-hand operand. E.g. `1 << 3` means `1*2*2*2`. – M.M Jan 13 '17 at 07:42
  • 2
    The `counter & (stuff)` results in a *bitwise* `AND` of `counter` and `stuff` – David C. Rankin Jan 13 '17 at 07:45
  • [What are bitwise shift (bit-shift) operators and how do they work?](http://stackoverflow.com/q/141525/995714) – phuclv Jan 13 '17 at 07:47

2 Answers2

31

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.

Azeem
  • 11,148
  • 4
  • 27
  • 40
Codor
  • 17,447
  • 9
  • 29
  • 56
1

---First for loop run i=0 to i<8 .(explanation - https://www.geeksforgeeks.org/power-set/)

---Second loop run i=0 to i<3 (for {a,b,c})

1.let's take for first loop i=0 :

    j=0,1,2 in this case (0 & (1<<0)),(0 & (1<<1)),(0 & (1<<2)) 
    
    But 0 with & is always 0 so all instance are false for first loop.

  1. let's take for second loop i=1 :

    j=0 int this case (1 & (1<<0)) it is true so j=0 and arr[0]=a print.

    j=1,2 are false because ( 1 & (1<<1)) & (1 & (1<<2)) are false.

  2. let's take for second loop i=2 :

    j=1, int this case (2 & (1<<1)) it is true so j=1 and arr[1]=b print.

    j=0,2 are false because ( 2 & (1<<0)) & (2 & (1<<2)) are false.

  3. let's take for second loop i=3 :

    j=0,2 int this case (3 & (1<<2)) & (3 & (1<<2)) it is true so j=0,2 and arr[2] =a & c print.

    j=1 are false because ( 3 & (1<<1)) are false.

  4. let's take for second loop i=4 :

    j=2 int this case (4 & (1<<2)) it is true so j=2 and arr[2] =c print.

    j=0,1 are false because ( 4 & (1<<0)) & (4 & (1<<1)) are false.

So this goes on.....

Vrutik Parajapati
  • 11
  • 4