在C#中对任意大的正整数进行位计数

Question

有许多位计数的实现，但在我的情况下，我需要测试一个任意大的数字是否最多包含两个设置的位。

我编写了以下函数来执行该任务，似乎相当快，但我想找出它能否在C#中进一步优化。这个函数在循环中调用了几百万次。

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

重要提示：传递给函数的参数[number]永远不会是负数。

我想到了一些点：

• 将函数设为静态。已完成。
• 使用静态查找数组。已完成。
• 使用指针而不是数组索引，因为字节数经常超过100,000。不确定这是否有帮助。
• 强制内联函数，但在.NET中无法保证。

欢迎其他建议。

- Raheel Khan

---

抱歉，我不确定我理解了。您说位计数，但您正在使用字节？ - Simon Whitehead

@SimonWhitehead：我们正在计算位。它们恰好作为字节数组可用。 - Raheel Khan

Answer 1

通过这种方式，您可以进一步优化它。

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;

- Narendra

---

е°†break;ж”№дёєreturn false;гЂ‚е°†return (sum < 3);ж”№дёєreturn true;。这样可以节省更多的循环。 - cadrell0

@cadrell0：是的，那样会更加优化。 - Narendra

Answer 2

既然您只需要知道是否有少于3个设置位，我建议这样做:

// remove two bits
number &= number - 1;
number &= number - 1;
// if number != 0, then there were 3 or more bits set
return number.IsZero;

当然，Rain的方法也可行，我不确定哪种策略会更快。

另一种选择：

//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;

最好先进行测试，之后再删除掉不需要的部分：

return number.IsZero ||        // zero bits?
    number.IsPowerOfTwo ||     // one bit?
    (number & (number - 1)).IsPowerOfTwo;  // two bits?

- harold

Answer 3

最明显的优化是在sum == 3时立即退出循环，因为在此之后的任何匹配都是无关紧要的。

另外，没有必要两次设置bytes；只需使用byte [] bytes = number.ToByteArray();即可，但这里的好处微乎其微。

- Dan Puzey