Lokesh and Bitwise Operators

Author : shailesh_2004

Required Knowledge : Bit Manipulation

Time Complexity : $O(30\cdot T)$

Editorialist : shailesh_2004

Approach:

Our task is to maximize the value of the given expression.

Let's consider each bit and decide the bit value of $x$ at that position.

Compare the values obtained by putting $0$ and $1$ separately in that position in the expression by taking only that position's values of other varibles.

Let $aa, bb, cc$ be the bit values at a certain position in $a, b, c$ respectively.

If we put $0$ at that position in $x$, the value is

$val1 =$ $((aa\&bb)$^$(cc\&0))$ $+$ $((bb$ $\mid$ $cc) \& (aa$ $\mid$ $0))$ $+$ $((cc$^$aa)$ $\mid$ $(bb$^$0))$

If we put $1$ at that position in $x$, the value is

$val2 =$ $((aa\&bb)$^$(cc\&1))$ $+$ $((bb$ $\mid$ $cc) \& (aa$ $\mid$ $1))$ $+$ $((cc$^$aa)$ $\mid$ $(bb$^$1))$

If $val1=val2$, then we have two choices of choosing $0$ or $1$ at that position.

Otherwise, we need to put the bit that maximizes the value i.e., we have only one choice based on which is higher among $val1$ and $val2$.

For each bit, we check $val1$ and $val2$ and apply basic Math to get the number of values possible for $x$.

Code:

// Author : Shailesh
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vll vector<ll>
#define pb push_back
#define mp make_pair
#define endl "\n"
#define mod 1000000007
#define tot(a) a.begin(),a.end()
#define minii *min_element
#define maxii *max_element

// ------------------------------------------------------------------------------------

void solve()
{
    ll a,b,c;
    cin>>a>>b>>c;
    ll i;
    ll ans=1;
    for(i=0;i<30;i++)
    {
        ll aa=0,bb=0,cc=0;
        if((1<<i)&(a))aa=(1<<i);
        if((1<<i)&(b))bb=(1<<i);
        if((1<<i)&(c))cc=(1<<i);
        ll x=0;
        ll xx=(1<<i);
        if((((aa&bb)^(cc&xx))+((bb|cc)&(aa|xx))+((cc^aa)|(bb^xx)))==
        (((aa&bb)^(cc&x))+((bb|cc)&(aa|x))+((cc^aa)|(bb^x))))ans*=2;
    }
    cout<<ans<<endl;
}

// ------------------------------------------------------------------------------------

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    ll t;cin>>t;while(t--)
    solve();
    return 0;
}