在C中查找整数中最高设置位(msb)的最快/最有效的方法是什么？
在C中查找整数中最高设置位(msb)的最快/最有效的方法是什么？
提问于 2009-03-23 07:37:23
如果我有一些整数n，并且我想知道最高有效位的位置(也就是，如果最低有效位在右边，我想知道最左边1位的位置)，那么找出最快/最有效的方法是什么？
我知道POSIX支持在strings.h中使用ffs()方法来查找第一个设置位，但是似乎没有对应的fls()方法。
有没有什么明显的方法是我没有注意到的？
如果不能使用POSIX函数实现可移植性，该怎么办呢？
编辑:一个同时适用于32位和64位体系结构的解决方案如何(许多代码清单似乎只适用于32位整数)。
回答 20
Stack Overflow用户
发布于 2009-03-23 00:32:11
这应该是闪电般的速度：
int msb(unsigned int v) {
static const int pos[32] = {0, 1, 28, 2, 29, 14, 24, 3,
30, 22, 20, 15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19,
16, 7, 26, 12, 18, 6, 11, 5, 10, 9};
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v = (v >> 1) + 1;
return pos[(v * 0x077CB531UL) >> 27];
}Stack Overflow用户
发布于 2011-12-11 15:43:14
Kaz Kylheku在这里
为此，我对两种方法进行了基准测试，超过63位数字( gcc x86_64上的long long类型)，远离符号位。
(你看，我碰巧需要这个“找到最高位”。)
我实现了数据驱动的二进制搜索(紧密基于上面的答案之一)。我还手动实现了一个完全展开的决策树，这只是带有立即操作数的代码。没有循环，没有表。
决策树(highest_bit_unrolled)的基准测试速度提高了69%，除了n=0的情况下，对分搜索进行了显式测试。
对于0的情况，二分搜索的特殊测试仅比没有特殊测试的决策树快48%。
编译器，机器：(GCC 4.5.2，-O3，x86-64,2867 Mhz Intel Core i5)。
int highest_bit_unrolled(long long n)
{
if (n & 0x7FFFFFFF00000000) {
if (n & 0x7FFF000000000000) {
if (n & 0x7F00000000000000) {
if (n & 0x7000000000000000) {
if (n & 0x4000000000000000)
return 63;
else
return (n & 0x2000000000000000) ? 62 : 61;
} else {
if (n & 0x0C00000000000000)
return (n & 0x0800000000000000) ? 60 : 59;
else
return (n & 0x0200000000000000) ? 58 : 57;
}
} else {
if (n & 0x00F0000000000000) {
if (n & 0x00C0000000000000)
return (n & 0x0080000000000000) ? 56 : 55;
else
return (n & 0x0020000000000000) ? 54 : 53;
} else {
if (n & 0x000C000000000000)
return (n & 0x0008000000000000) ? 52 : 51;
else
return (n & 0x0002000000000000) ? 50 : 49;
}
}
} else {
if (n & 0x0000FF0000000000) {
if (n & 0x0000F00000000000) {
if (n & 0x0000C00000000000)
return (n & 0x0000800000000000) ? 48 : 47;
else
return (n & 0x0000200000000000) ? 46 : 45;
} else {
if (n & 0x00000C0000000000)
return (n & 0x0000080000000000) ? 44 : 43;
else
return (n & 0x0000020000000000) ? 42 : 41;
}
} else {
if (n & 0x000000F000000000) {
if (n & 0x000000C000000000)
return (n & 0x0000008000000000) ? 40 : 39;
else
return (n & 0x0000002000000000) ? 38 : 37;
} else {
if (n & 0x0000000C00000000)
return (n & 0x0000000800000000) ? 36 : 35;
else
return (n & 0x0000000200000000) ? 34 : 33;
}
}
}
} else {
if (n & 0x00000000FFFF0000) {
if (n & 0x00000000FF000000) {
if (n & 0x00000000F0000000) {
if (n & 0x00000000C0000000)
return (n & 0x0000000080000000) ? 32 : 31;
else
return (n & 0x0000000020000000) ? 30 : 29;
} else {
if (n & 0x000000000C000000)
return (n & 0x0000000008000000) ? 28 : 27;
else
return (n & 0x0000000002000000) ? 26 : 25;
}
} else {
if (n & 0x0000000000F00000) {
if (n & 0x0000000000C00000)
return (n & 0x0000000000800000) ? 24 : 23;
else
return (n & 0x0000000000200000) ? 22 : 21;
} else {
if (n & 0x00000000000C0000)
return (n & 0x0000000000080000) ? 20 : 19;
else
return (n & 0x0000000000020000) ? 18 : 17;
}
}
} else {
if (n & 0x000000000000FF00) {
if (n & 0x000000000000F000) {
if (n & 0x000000000000C000)
return (n & 0x0000000000008000) ? 16 : 15;
else
return (n & 0x0000000000002000) ? 14 : 13;
} else {
if (n & 0x0000000000000C00)
return (n & 0x0000000000000800) ? 12 : 11;
else
return (n & 0x0000000000000200) ? 10 : 9;
}
} else {
if (n & 0x00000000000000F0) {
if (n & 0x00000000000000C0)
return (n & 0x0000000000000080) ? 8 : 7;
else
return (n & 0x0000000000000020) ? 6 : 5;
} else {
if (n & 0x000000000000000C)
return (n & 0x0000000000000008) ? 4 : 3;
else
return (n & 0x0000000000000002) ? 2 : (n ? 1 : 0);
}
}
}
}
}
int highest_bit(long long n)
{
const long long mask[] = {
0x000000007FFFFFFF,
0x000000000000FFFF,
0x00000000000000FF,
0x000000000000000F,
0x0000000000000003,
0x0000000000000001
};
int hi = 64;
int lo = 0;
int i = 0;
if (n == 0)
return 0;
for (i = 0; i < sizeof mask / sizeof mask[0]; i++) {
int mi = lo + (hi - lo) / 2;
if ((n >> mi) != 0)
lo = mi;
else if ((n & (mask[i] << lo)) != 0)
hi = mi;
}
return lo + 1;
}快速和肮脏的测试程序：
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
int highest_bit_unrolled(long long n);
int highest_bit(long long n);
main(int argc, char **argv)
{
long long n = strtoull(argv[1], NULL, 0);
int b1, b2;
long i;
clock_t start = clock(), mid, end;
for (i = 0; i < 1000000000; i++)
b1 = highest_bit_unrolled(n);
mid = clock();
for (i = 0; i < 1000000000; i++)
b2 = highest_bit(n);
end = clock();
printf("highest bit of 0x%llx/%lld = %d, %d\n", n, n, b1, b2);
printf("time1 = %d\n", (int) (mid - start));
printf("time2 = %d\n", (int) (end - mid));
return 0;
}仅使用-O2，差异会变得更大。决策树的速度几乎快了四倍。
我还对简单的位移位代码进行了基准测试：
int highest_bit_shift(long long n)
{
int i = 0;
for (; n; n >>= 1, i++)
; /* empty */
return i;
}正如人们所预期的那样，这只适用于较小的数字。在确定n == 1的最高位为1时，它的基准测试速度快了80%以上。然而，63位空间中随机选择的数字中有一半设置了63位！
在输入0x3FFFFFFFFFFFFFFFFFFF上，决策树版本比在1上快很多，并且比位移位器快1120% (12.2倍)。
我还将针对GCC内置的决策树进行基准测试，并尝试混合输入，而不是针对相同的数字重复输入。可能有一些粘滞的分支预测正在进行，也可能有一些不切实际的缓存场景，这使得它在重复时人为地加快了速度。
Stack Overflow用户
发布于 2009-03-23 03:21:46
unsigned int
msb32(register unsigned int x)
{
x |= (x >> 1);
x |= (x >> 2);
x |= (x >> 4);
x |= (x >> 8);
x |= (x >> 16);
return(x & ~(x >> 1));
}1个寄存器，13条指令。信不信由你，这通常比上面提到的BSR指令更快，后者在线性时间内运行。这是对数时间。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/671815
复制相关文章
相似问题
腾讯云开发者
