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.comstackoverflow.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));
}