# Hackerrank Sum vs XoR

Posted on

Problem

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$n$$n$ , find each x$x$$x$ such that:

0xn$0\le x\le n$$0 leq x leq n$

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

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

## Input Format

A single integer, n$n$$n$ .

## Constraints

0n1015$0\le n\le {10}^{15}$$0 leq n leq 10 ^ {15}$

0n100$0\le n\le 100$$0 leq n leq 100$ for 60%$60\mathrm{%}$$60%$ of the maximum score

## Output Format

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

Sample Input 0

5


Sample Output 0

2


Explanation 0

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

Thus, we print 2$2$$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) {
Console.WriteLine(SumVsXoR(n));
}
}


Solution

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

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

Where:

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

So we just need to calculate the number of zero bits in the n$n$$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));
}