user5956891 user5956891 - 3 months ago 40
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
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(;
long n = in.nextLong();
int cnt=0;
for(long i=0;i<=n;i++)
long m=i^n;


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.