Bit counting arbitrarily large positive integers in C#

Question

There are many implementations of bit counting out there but in my case, I need to test if an arbitrarily large number contains at most two set bits.

I wrote the following function that does the job and seems to be quite fast but I wanted to find out if it can be further optimized for C#. This function gets called in a loop a few million times.

public static byte [] BitCountLookupArray = new byte []
{
    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};

// The parameter [number] will NEVER be negative.
public static bool HasSetBitCountOfLessThenThree (System.Numerics.BigInteger number)
{
    int sum = 0;
    byte [] bytes = null;

    bytes = number.ToByteArray();

    for (int i=0; i < bytes.Length; i++)
    {
        sum += BitCountLookupArray [bytes [i]];
    }

    return (sum < 3);
}

IMPORTANT: The argument [number] sent to the function will NEVER be negative.

Some points I thought of were:

• Making the function static. Done.
• Using a static lookup array. Done.
• Using pointers instead of array indexes since the number of bytes often crosses 100,000. Not sure how much this would help.
• Forcing an inline function which sadly cannot be guaranteed in .NET.

Open to other suggestions.

Answer 1

This way you can optimise it further

for (int i=0; i < bytes.Length; i++)
{
    sum += BitCountLookupArray [bytes [i]];
    if(sum >= 3)
    {
         return false   // This will stop the execution of unnecessary lines  
                        // as we need to know whether sum is less than 3 or not.                         
    }
}

return true;