Skip to main content
replaced http://stackoverflow.com/ with https://stackoverflow.com/
Source Link

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

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

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));
}
deleted 11 characters in body
Source Link
Dmitry
  • 4.6k
  • 1
  • 19
  • 32

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 (int)Math.Pow(2,1 << (numberOfBits - NumberOfSetBits(number));
}

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 (int)Math.Pow(2, numberOfBits - NumberOfSetBits(number));
}

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));
}
added 4 characters in body
Source Link
Dmitry
  • 4.6k
  • 1
  • 19
  • 32

Let us noteLet's notice that
\$ n + x = n \oplus x \$ is true
onlywhen and only when
\$ n + x = n \cup x \$\$ n + x = n \vee x \$ is true

This is because \$ n + x \geq n \cup x = n \oplus x + n \cap x \$\$ n + x \geq n \vee x = n \oplus x + n \wedge x \$.

Where:

  • \$ \cap \$\$ \vee \$ - logicalbitwise OR
  • \$ \cup \$\$ \wedge \$ - logicalbitwise 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 (int)Math.Pow(2, numberOfBits - NumberOfSetBits(number));
}

Let us note that
\$ n + x = n \oplus x \$ is true
only when
\$ n + x = n \cup x \$ is true

This is because \$ n + x \geq n \cup x = n \oplus x + n \cap x \$.

Where:

  • \$ \cap \$ - logical OR
  • \$ \cup \$ - logical 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 (int)Math.Pow(2, numberOfBits - NumberOfSetBits(number));
}

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 (int)Math.Pow(2, numberOfBits - NumberOfSetBits(number));
}
Source Link
Dmitry
  • 4.6k
  • 1
  • 19
  • 32
Loading