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 , find each x such that:
0≤x≤n
n+x=n⊕x
where ⊕ 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≤n≤1015
Subtasks
0≤n≤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));
}
}
Solution
Let’s notice that
n+x=n⊕x is true
when and only when
n+x=n∨x is true
This is because
n+x≥n∨x=n⊕x+n∧x.
Where:
- ∨ – bitwise OR
- ∧ – 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));
}