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, nn , find each xx such that:

0xn0xn

n+x=nxn+x=nx

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

Input Format

A single integer, nn .

Constraints

0n10150n1015

Subtasks

0n1000n100 for 60%60% of the maximum score

Output Format

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

Sample Input 0

5

Sample Output 0

2

Explanation 0

For n=5n=5 , the xx values 00 and 22 satisfy the
conditions:

Thus, we print 22 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=nxn+x=nx is true
when and only when
n+x=nxn+x=nx is true

This is because
n+xnx=nx+nxn+xnx=nx+nx.

Where:

  • – bitwise OR
  • – bitwise AND

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

Leave a Reply

Your email address will not be published. Required fields are marked *