4
\$\begingroup\$

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));
    }
}
\$\endgroup\$
4
\$\begingroup\$

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));
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.