user5956891 user5956891 - 1 month ago 9
Java Question

Sum vs XOR menas x+a=x^a ,

Given an integer, , find each such that:
x+a=x^a ,
where denotes the bit wise XOR operator. Then print an integer denoting the total number of x's satisfying the criteria above.
for example a=5 then x=0,2
a+x=a^x;
I tried to solve this way. Is there any other way to reduce time complexity.

`public static void main(String[] args) {
Scanner in = new Scanner(System.in);
long n = in.nextLong();
int cnt=0;
for(long i=0;i<=n;i++)
{
long m=i^n;
if(n+i==m)
cnt++;
}
System.out.println(cnt);
}`

Answer

n can have any bit not set in a and this formula will hold.

This means the number of bits to permutate will be 32 minus the number of bits set in a i.e. Integer.bitCount

long cnt = 1L << (32 - Integer.bitCount(a));

Note if a has 0 or 1 bit set, the number of solutions is greater than Integer.MAX_VALUE.