Hackerrank Sum vs XoR

Question

I'm in the process of improving my coding style and performance hence I decided to delve into bit manipulation on Hackerrank. I thought the question was straight forward but on large input, my solution's performance declines. How do I improve it? Any smart tricks to solve the below question is welcome as well.

Below is the question

Given an integer, \$n\$ , find each \$x\$ such that:

\0ドル \leq x \leq n \$

\$ n + x = n \oplus x \$

where \$\oplus\$ denotes the bitwise XOR operator. Then print an integer denoting the total number of \$x\$ 's satisfying the criteria above.

Input Format

A single integer, \$n\$ .

Constraints

\0ドル \leq n \leq 10 ^ {15}\$

Subtasks

\0ドル \leq n \leq 100\$ for \60ドル\%\$ of the maximum score

Output Format

Print the total number of integer \$x\$ 's satisfying both of the conditions specified above.

Sample Input 0

5

Sample Output 0

2

Explanation 0

For \$n = 5\$ , the \$x\$ values \0ドル\$ and \2ドル\$ satisfy the conditions:

Thus, we print \2ドル\$ as our answer.

---

Here is my code

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
 static int SumVsXoR(long number)
 {
 int count =0;
 long j = 0;
 while (j <= number)
 { 
 if(j + number == (j^number)){ 
 count++; 
 }
 j++;
 }
 return count;
 }
 static void Main(String[] args) {
 long n = Convert.ToInt64(Console.ReadLine());
 Console.WriteLine(SumVsXoR(n));
 }
}

Answer 1

Let's notice that
\$ n + x = n \oplus x \$ is true
when and only when
\$ n + x = n \vee x \$ is true

This is because \$ n + x \geq n \vee x = n \oplus x + n \wedge x \$.

Where:

• \$ \vee \$ - bitwise OR
• \$ \wedge \$ - bitwise AND

So we just need to calculate the number of zero bits in the \$n\$.
Let's calculate the nonzero bits:

private static int NumberOfSetBits(ulong i)
{
 i = i - ((i >> 1) & 0x5555555555555555UL);
 i = (i & 0x3333333333333333UL) + ((i >> 2) & 0x3333333333333333UL);
 return (int)(unchecked(((i + (i >> 4)) & 0xF0F0F0F0F0F0F0FUL) * 0x101010101010101UL) >> 56);
}

The method above was copy-pasted from this answer: stackoverflow.com

Then rewrite the SumVsXoR method:

private static int SumVsXoR(ulong number)
{
 int numberOfBits = (int)Math.Log(number, 2) + 1;
 return 1 << (numberOfBits - NumberOfSetBits(number));
}