nr: #1 dodano: 20170105 07:01
The problem with your code is that it is very inefficient. For the case of n==1000000000000000 , your Stream pipeline is performing 1,000,000,000,000,000 addition and XOR operations, which takes a long time. Testing for each number between 0 and n whether n + x == n ^ x would take a long time even if you use a for loop instead of Stream s.
Instead of checking all the numbers between 0 and n, you should try to figure out a better way to calculate the required total number of x's. That fact that this problem appears under a "Bit Manipulation" section should give you a hint
to look into the bits of numbers that satisfy n + x == n ^ x .
Let's consider the case of n==1000000000000000 . The binary representation of that large number is
0000000000000011100011010111111010100100110001101000000000000000
=== == = ====== = = = == == =
         
~~~~~~~~~~~~~~
In order for n + x to be equal to n ^ x , x must have a 0 value in all the bits corresponding with the 1 bits of n (marked with = above), and either 0 or 1 value in the bits corresponding with the 0 bits of n (marked with  above). This doesn't include the leading 0 s (marked with ~ above), since x must be <= n , so any leading 0 s in n must also have a 0 value in x .
This means that the total number of x's for which n + x == n ^ x is 2^{the number of 0s in n, not including leading 0s}.
In the case of n = 1000000000000000 , there are 30 such 0 bits, so the total number of x 's that satisfy the requirement is 2^{30}.
Here's one way to compute the total number of x 's :
long n = 1000000000000000L;
int zeroBitsCount = 0;
while (n > 0) {
if (n % 2 == 0) {
zeroBitsCount++; // counts the number of nonleading 0 bits
}
n = n >> 1; // divide n by 2 in order to examine the next bit in the next iteration
}
long total = 1L << zeroBitsCount; // the total is 2^(the 0 bits count)
