XOR programming puzzle advice

Given a long int x, count the number of values of a that satisfy the following conditions:

a XOR x > x
0 < a < x

where a and x are long integers and XOR is the bitwise XOR operator

How would you go about completing this problem?

I should also mentioned that the input x can be as large as 10^10

I have managed to get a brute force solution by iterating over 0 to x checking the conditions and incrementing a count value.. however this is not an optimal solution...

This is the brute force that I tried. It works but is extremely slow for large values of x.

 for(int i =0; i < x; i++)
 {
      if((0 < i && i < x) && (i ^ x) > x)
          count++;    
 }

Solution

long long NumberOfA(long long x)
{
    long long t = x <<1;
    while(t^(t&-t)) t ^= (t&-t);
    return t-++x;
}


long long x = 10000000000;
printf("%lld ==> %lld\n", 10LL, NumberOfA(10LL) ); 
printf("%lld ==> %lld\n", x, NumberOfA(x) );

Output

10 ==> 5
10000000000 ==> 7179869183

Link to IDEOne Code

Trying to explain the logic (using example 10, or 1010b)

Shift x to the left 1. (Value 20 or 10100b)
Turn off all low bits, leaving just the high bit (Value 16 or 10000b)
Subtract x+1 (16 - 11 == 5)

Attempting to explain
(although its not easy)

Your rule is that a ^ x must be bigger than x, but that you cannot add extra bits to a or x.
(If you start with a 4-bit value, you can only use 4-bits)

The biggest possible value for a number in N-bits is 2^n -1.
(eg. 4-bit number, 2^4-1 == 15)
Lets call this number B.

Between your value x and B (inclusive), there are B-x possible values.
(back to my example, 10. Between 15 and 10, there are 5 possible values: 11, 12, 13, 14, 15)

In my code, t is x << 1, then with all the low bits turned off.
(10 << 1 is 20; turn off all the low bits to get 16)

Then 16 - 1 is B, and B - x is your answer:
(t - 1 - x, is the same as t - ++x, is the answer)