c# - 如何找出最快的算法

Question

在计算一个字中的位数时，暴力破解会是这样的:

int CountNumSetBits(unsigned long n)
{
    unsigned short num_setbits = 0;
    while (n)
    {
        num_setbits += n & 1;
        n >>= 1;
    }
    return num_setbits;
}

大 O 速度将为 O(n)，其中 n 是字中的位数。

我想到了另一种编写算法的方法，利用这样的事实:我们可以使用 y = x&~(x-1) 来获取设置位的第一次出现

int CountNumSetBitsMethod2(unsigned long n)
{
    unsigned short num_setbits = 0;
    int y = 0;
    while (n)
    {
        y = n& ~(n - 1); // get first occurrence of '1'
        if (y) // if we have a set bit inc our counter
            ++num_setbits;
        n ^=y;  // erase the first occurrence of '1'
    }
    return num_setbits;
}

如果我们假设输入有 50% 为 1 和 50% 为 0，那么第二种算法的速度似乎会快两倍。然而，实际的复杂性更大:

在方法一中，我们对每一位执行以下操作: 1 添加 1 和 1类

在方法二中，我们对每个设置位执行以下操作: 1 和 1 补码 1 次减法(减法结果必须复制到另一个寄存器) 1 比较 1 增量(如果比较为真) 1 异或

现在，在实践中，人们可以通过执行一些分析来确定哪种算法更快。也就是说，使用秒表机制和一些测试数据并调用每个算法一百万次。

然而，我首先想做的是通过观察代码来看看我能在多大程度上估计速度差异(给定相同数量的设置和未设置位)。

如果我们假设减法与加法所花费的周期数(大约)相同，并且所有其他操作的周期数相同，那么我们是否可以得出结论，每种算法花费的时间大约相同？

注意:我假设这里我们不能使用查找表。

Answer 1

第二种算法可以大大简化:

int CountNumSetBitsMethod2(unsigned long n) {
    unsigned short num_setbits = 0;
    while (n) {
        num_setbits++;
        n &= n - 1;
    }
    return num_setbits;
}

还有很多方法可以计算一个字中设置的位数:

• 一次使用多个位的查找表
• 使用 64 位乘法
• 使用并行加法
• 使用额外的技巧来缩短周期。

尝试通过计算周期来凭经验确定哪个更快并不那么容易，因为即使查看汇编输出，也很难评估指令并行化、流水线、分支预测、寄存器重命名和争用的影响......现代 CPU 非常复杂!此外，生成的实际代码取决于编译器版本和配置，计时取决于 CPU 类型和版本...更不用说与所使用的特定值集相关的可变性(对于指令数量可变的算法)。

基准测试是必要的工具，但即使仔细的基准测试也可能无法正确模拟实际使用情况。

这里有一个很棒的网站，可以玩这种无聊的游戏:

http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

我建议您实现不同的版本并在您的系统上执行比较基准测试。没有明确的答案，只有特定条件下的局部最优。

一些惊人的发现:

// option 3, for at most 32-bit values in v:
c =  ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) % 
     0x1f;
c += ((v >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;

一种更经典的方法，通常被认为是计算 32 位整数 v 中位数的最佳方法:

v = v - ((v >> 1) & 0x55555555);                    // reuse input as temporary
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count