Inclusion exclusion principle implementation

#1

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
int t;cin>>t;
int primes[]={2,3,5,7,11,13,17,19};
while(t–)
{
ll n;
cin>>n;

    ll subsets=(1<<8)-1;// -1 
    ll ans=0;
    for(ll i=1;i<=subsets;i++)
    {
        ll denom=1ll;
        ll setbits=__builtin_popcount(i);                                             
           for(ll j=0;j<8;j++)                    
        {              
            if(i&(1<<j))
            {
                denom=denom*primes[j];
            }
        }

        if(setbits&1){
            ans+=n/denom;
        }
        else
        {
            ans-=n/denom;
        }
    }
    cout<<ans<<endl;

}

return 0;

}

sir can you explain this contidion

if(1&(1<<j))
{
denom=denom*primes[j]
}

how we are checking this by which number we have check

#2

So what happens is that i iterates from 1 to (2^n-1), if n is the number of elements in the set.
If you represent i in terms of binary, we are always seeing it as a n bit number where each bit corresponds to a particular element. So if it’s 1 then that number is selected in the subset and 0 means it’s not.
So lets consider a particular i while looping. Now if jth bit is 1 in ‘i’, it means we need to select that element corresponding to the jth bit. (1<<j) is simply setting the jith bit, and when we do bitwise and, we can know if jth bit is set in i or not.

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.