获得前导1位的数量

Question

给定无符号数,获得前导1位数的好方法(最好是快速方法)是什么？

我需要这个来计算四点IPv4网络掩码的CIDR数.

注意:我已经看到了得到尾随数1位,所以我可以进行基于表的查找.

注2:尽管我添加了几个语言标签,但对我来说这是关于算法的,所以如果你有一个很好的用另一种语言,请随时发布.

编辑:关于endian-ness.

我刚刚发现INET_ADDR函数和IN_ADDR结构以big-endian形式存储IPv4地址,而x86是little-endian,我使用的大多数处理器也是little-endian.
因此,针对此特定情况的查找表足够快.
但是感谢其他答案:他们在更常见的情况下工作得非常好.

--jeroen

Answer 1

如果反转所有位,则可以使用前导检测算法(相当于log2算法); 参见例如http://www-graphics.stanford.edu/~seander/bithacks.html.您可以修改其中一些算法,并跳过反转阶段.

Answer 2

如果1之前的所有位都是0，则可以使用BSF汇编指令，它将返回从低位开始的第一个位组（非零）的索引，然后您可以用32减去它并获得位数放。
否则，如果您必须从高位开始查找，您可以使用NOT来反转这些位，并使用BSR从高位扫描到零。

Answer 3

除非你专门寻找步数(即O(lg(n))的位数的理论改进,否则我认为你实际上不会比表查找做得更好,并且仍然有一个可移植的算法.

我希望在现代机器上的单个线程上使用简单的表查找来轻松扫描超过1亿个IPv4网络掩码,以获得每秒领先的网络掩码(不包括实际获取IPv4网络掩码的工作).我不确定进一步算法改进的收益是否值得任何增加的复杂性.

Answer 4

这个问题虽然完全不相关，但显示了一些用于执行 CTZ/CLZ（计数前导/尾随零）的 C 代码。如果在调用其中之一之前反转（不按位）输入，您可以获得前导/尾随的数量。