user5956891 - 11 months ago 93

Java Question

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 Source

`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.