2

C++ code. In this code, I got confused while I read the code. As you can see (i & (j<<1)) in that condition does it mean an odd number? Please let me know (i & (j<<1)) what does it mean is and how does it work?

void solve()
{
    int n, l, r, x;
    cin >> n >> l >> r >> x;
 
    int a[1000];
 
    for(int i=0; i<n; i++)
    cin >> a[i];
 
    int ans=0;
 
    for(int i=0; i< (1<<n); i++)
    {
        if(__builtin_popcount(i) >= 2)
        {
            int mx=0;
            int mn=INT_MAX;
 
            int sum=0;
 
            for(int j=0; j<n; j++)
            {
                if(i & (1<<j)) /// What does it mean ??
                {
                    sum+=a[j];
 
                    mx=max(mx, a[j]);
                    mn=min(mn, a[j]);
                }
            }
 
            if(l <= sum && sum<=r && mx-mn>=x)
            ans++;
        }
    }
 
    cout << ans << '\n';
}
einpoklum
  • 118,144
  • 57
  • 340
  • 684
Shipul Roy
  • 54
  • 5
  • see if you can work it out, lookup what & means , lookup what << means. – pm100 Feb 07 '22 at 23:46
  • Read up about [bitwise shift operators](https://en.cppreference.com/w/cpp/language/operator_arithmetic#Bitwise_shift_operators) (`<<` and `>>`) and the [bitwise `AND` operator](https://en.cppreference.com/w/cpp/language/operator_arithmetic#Bitwise_logic_operators) (`&`) – Remy Lebeau Feb 07 '22 at 23:46

1 Answers1

4
if(i & (1<<j))

means "if the binary representation of i has its j'th (lowest) bit turned on".

That's because:

Caveat: n must be low enough so that (1<<j) doesn't exceed the number of bits in an int (which depends on the platform)... otherwise bad things may happen.

einpoklum
  • 118,144
  • 57
  • 340
  • 684
  • 1
    Re “doesn't exceed the number of bits”: If the shift amount equals the number of bits, the behavior is not defined by the C standard. Re “otherwise you'll just get 0”: The behavior is not defined by the C standard. – Eric Postpischil Feb 07 '22 at 23:55