如何计算32位无符号整数中的前导零

Question

有谁能告诉我什么是一个有效的算法来计算C编程中32位无符号整数中前导零的数量？

Answer 1

此讨论假定您的编译器不支持该操作,或者它不能产生足够好的程序集.请注意,现在这两种情况都不太可能,所以我建议您只__builtin_clz在编译器上使用gcc或等效代码.

请注意,确定哪个是"最佳"clz算法只能由您完成.现代处理器是复杂的动物,这些算法的性能将在很大程度上取决于您运行它的平台,您投入的数据以及使用它的代码.唯一可以确定的方法是测量,测量和测量更多.如果你无法区分,那么你可能没有看到你的瓶颈,你的时间会更好地花在其他地方.

现在无聊的免责声明已经不在了,让我们来看看Hacker's Delight对这个问题的看法.一项快速调查显示,所有算法都依赖于某些描述的二进制搜索.这是一个简单的例子:

int n = 32;
unsigned y;

y = x >>16; if (y != 0) { n = n -16; x = y; }
y = x >> 8; if (y != 0) { n = n - 8; x = y; }
y = x >> 4; if (y != 0) { n = n - 4; x = y; }
y = x >> 2; if (y != 0) { n = n - 2; x = y; }
y = x >> 1; if (y != 0) return n - 2;
return n - x;

请注意,这适用于32个整数,如果需要,它也可以转换为迭代版本.不幸的是,这个解决方案并没有很多指令级的并行性,并且有很多分支,这些分支并没有形成一个非常好的位.请注意,上面代码的分支免费版本存在,但它更详细,所以我不会在这里重现.

因此,让我们通过使用pop指令(计算位数)来改进解决方案:

x = x | (x >> 1);
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >>16);
return pop(~x);

那么这是如何工作的呢？关键是最后的pop(~x)指令,它计算了零的数量x.为了使零的计数有意义,我们首先需要摆脱不领先的所有0.我们通过使用二进制算法正确传播1来做到这一点.虽然我们仍然没有太多的指令级并行性,但我们确实摆脱了所有分支,并且它比先前的解决方案使用更少的周期.好多了.

那么流行教学怎么样,不是作弊？大多数架构都有一个1周期弹出指令,可以通过编译器内置程序(例如gcc __builtin_pop)访问.否则存在基于表的解决方案,但是当关闭高速缓存访​​问的周期时必须小心,即使该表完全保存在L1高速缓存中.

最后,正如黑客的喜悦一样,我们开始在陌生的地区游荡.让我们用浮点数计算一些前导零:

union {
    unsigned asInt[2];
    double asDouble;
};
asDouble = (double)k + 0.5;
return 1054 - (asInt[LE] >> 20);

首先,一点警告:不要使用这种算法.就标准而言,这会触发未定义的行为.这比任何实际用途都更有趣.使用自负.

现在免责声明已经不在了,它是如何运作的？它首先将int转换为double,然后继续提取double的指数分量.整洁的东西.如果在小端机器上执行,LE常量应为1,在大端机器上执行0.

这应该为您简要介绍一下这个问题的各种比特算法.请注意,这本书有几种不同的变化,可以进行各种权衡,但我会让你自己发现这些.

Answer 2

这可能是在纯C中执行此操作的最佳方式:

int clz(uint32_t x)
{
    static const char debruijn32[32] = {
        0, 31, 9, 30, 3, 8, 13, 29, 2, 5, 7, 21, 12, 24, 28, 19,
        1, 10, 4, 14, 6, 22, 25, 20, 11, 15, 23, 26, 16, 27, 17, 18
    };
    x |= x>>1;
    x |= x>>2;
    x |= x>>4;
    x |= x>>8;
    x |= x>>16;
    x++;
    return debruijn32[x*0x076be629>>27];
}

一个限制:写入时,它不支持零输入(结果应为32).如果所有输入都小于0x80000000,则可以通过将表中的第一个值更改为32来支持零而无需额外成本.否则,只需在开头添加一行:

    if (!x) return 32;

Answer 3

让我们计算一下不包含前导零的位数。之后我们就做(32 - n)。首先，如果数字为零，则 n 为零。否则：

n = 1 + floor(log2(x))

也就是说，我们使用以 2 为底的对数来找出最高有效非零位的位置。我们可以使用计算 log2 的 FYL2X 指令在 x86 上高效地完成此操作。

但现在我们谈论的是 x86 指令，我们不妨看看真正可用的指令。这里是！http://en.wikipedia.org/wiki/Find_first_set - 您可以看到那里有很多指令可以直接执行您想要的操作 - 如果您愿意编写汇编或至少确认您的优化编译器生成这些指令为你给出了一些精心编写的C代码。