Bit counting arbitrarily large positive integers in C#
-
25-06-2021 - |
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.
Solution
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;
OTHER TIPS
Since you only need to know whether you have fewer than 3 set bits, I would suggest this:
// remove two bits
number &= number - 1;
number &= number - 1;
// if number != 0, then there were 3 or more bits set
return number.IsZero;
Of course Rain's method works too, and I'm not sure which strategy will be faster.
Alternative:
//remove one bit
number &= number - 1;
// if the number of bits left is 0 or 1, there were < 3 bits set
return number.IsZero || number.IsPowerOfTwo;
It's probably faster to test first, and remove the bit later:
return number.IsZero || // zero bits?
number.IsPowerOfTwo || // one bit?
(number & (number - 1)).IsPowerOfTwo; // two bits?
The most obvious optimisation is to drop out of the loop as soon as sum == 3
, since any further matches past that point are immaterial.
There's also no need to set bytes
twice; simply use byte [] bytes = number.ToByteArray();
, but the benifit here is miniscule.