3

有很多位计数的实现，但就我而言，我需要测试一个任意大的数字是否最多包含两个设置位。

我编写了以下函数来完成这项工作，而且看起来速度相当快，但我想知道它是否可以针对 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 中无法保证的内联函数。

接受其他建议。

4

3 回答 3

5

这样你可以进一步优化它

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;
于 2012-08-07T13:05:22.577 回答
3

由于您只需要知道您的设置位是否少于 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?
于 2012-08-07T15:50:01.250 回答
1

最明显的优化是尽快退出循环sum == 3，因为超过该点的任何进一步匹配都是无关紧要的。

也无需设置bytes两次；简单地使用byte [] bytes = number.ToByteArray();，但这里的好处是微乎其微的。

于 2012-08-07T13:05:49.007 回答