如果我有一个整数n,并且我想知道最高位的位置(也就是说,如果最低有效位在右边,我想知道最左边位的位置是1),找出最快捷/最有效的方法是什么？
我知道POSIX支持ffs()strings.h中的一个方法来查找第一个设置位,但似乎没有相应的fls()方法.
是否有一些非常明显的方法可以解决这个问题？
如果你不能使用POSIX功能来实现可移植性呢？
编辑:如何在32位和64位架构上运行的解决方案(许多代码清单似乎只能在32位整数上运行).
GCC有:
-- Built-in Function: int __builtin_clz (unsigned int x)
Returns the number of leading 0-bits in X, starting at the most
significant bit position. If X is 0, the result is undefined.
-- Built-in Function: int __builtin_clzl (unsigned long)
Similar to `__builtin_clz', except the argument type is `unsigned
long'.
-- Built-in Function: int __builtin_clzll (unsigned long long)
Similar to `__builtin_clz', except the argument type is `unsigned
long long'.
我希望它们能够被翻译成当前平台的合理效率,无论是那些花哨的比特算法还是单个指令.
如果你输入一个有用的技巧可以是零是__builtin_clz(x | 1):无条件设置低位,而无需修改任何其他使输出0的x=0,在不改变输出的任何其他输入.
为避免需要这样做,您的另一个选择是特定于平台的内在函数,如ARM GCC __clz(不需要头),或_lzcnt_u32支持该lzcnt指令的CPU上的x86 .(注意在较旧的CPU上lzcnt解码bsr而不是故障,这为非零输入提供31-lzcnt.)
遗憾的是,没有办法可以利用非x86平台上的各种CLZ指令,这些指令将input = 0的结果定义为32或64(根据操作数宽度).x86也是lzcnt这样做的,同时bsr产生一个比特索引,除非你使用,否则编译器必须翻转31-__builtin_clz(x).
("未定义的结果"不是C未定义的行为,只是一个未定义的值.它实际上是指令运行时目标寄存器中的任何内容.AMD记录了这一点,英特尔没有,但英特尔的CPU确实实现了这种行为但是,这并不是你以前在C变量中分配的任何东西,当gcc将C变成asm时,通常不会发生什么.参见为什么打破LZCNT的"输出依赖"很重要？)
假设您使用的是x86和游戏中的一些内联汇编程序,英特尔会提供一条BSR指令("位扫描反转").这是快上一些 x86s(微代码对他人).从手册:
在源操作数中搜索最重要的设置位(1位).如果找到最高1位,则其位索引存储在目标操作数中.源操作数可以是寄存器或存储器位置; 目标操作数是一个寄存器.位索引是源操作数的位0的无符号偏移量.如果内容源操作数为0,则目标操作数的内容未定义.
(如果你在PowerPC上有类似的cntlz("计数前导零")指令.)
gcc的示例代码:
#includeint main (int,char**) { int n=1; for (;;++n) { int msb; asm("bsrl %1,%0" : "=r"(msb) : "r"(n)); std::cout << n << " : " << msb << std::endl; } return 0; }
另请参阅此内联汇编程序教程,该教程显示(第9.4节)它比循环代码快得多.
由于2 ^ N是仅具有第N位设置的整数(1 << N),因此找到最高设置位的位置(N)是该整数的整数对数基数2.
http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious
unsigned int v;
unsigned r = 0;
while (v >>= 1) {
r++;
}
这"明显"的算法可能不是透明的,每个人,但是当你意识到代码移动向右一位,直到最左边位已被拿下(注意是c对待任何非零值作为真)并返回数量轮班,这很有道理.它还意味着即使设置了多个位也能工作 - 结果始终是最重要的位.
如果向下滚动该页面,则会有更快,更复杂的变化.但是,如果你知道你正在处理的数字有很多前导零的,天真的方法可以提供可接受的速度,因为位移位在C相当快,并且简单的算法不需要索引的数组.
注意:使用64位值时,要非常小心使用超灵巧算法; 其中许多只能正常工作32位值.
这应该是闪电般的:
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];
}
这有点像找一种整数日志.有点蠢蠢欲动,但我已经为此制作了自己的工具.当然,目标是速度.
我的意识是CPU已经有一个自动位检测器,用于整数到浮点转换!所以使用它.
double ff=(double)(v|1); return ((*(1+(uint32_t *)&ff))>>20)-1023; // assumes x86 endianness
此版本将值转换为double,然后读取指数,该指数告诉您该位的位置.花式移位和减法是从IEEE值中提取适当的部分.
使用浮点数稍快一些,但浮点数只能给你前24位的位置,因为它的精度较低.
为了安全地执行此操作,在C++或C中没有未定义的行为,请使用memcpy而不是指针转换来进行类型惩罚.编译器知道如何有效地内联它.
// static_assert(sizeof(double) == 2 * sizeof(uint32_t), "double isn't 8-byte IEEE binary64"); // and also static_assert something about FLT_ENDIAN? double ff=(double)(v|1); uint32_t tmp; memcpy(&tmp, ((const char*)&ff)+sizeof(uint32_t), sizeof(uint32_t)); return (tmp>>20)-1023;
或者在C99及更高版本中,使用a union {double d; uint32_t u[2];};.但请注意,在C++中,联合类型双关语仅在某些编译器上作为扩展支持,而不是在ISO C++中.
这通常比前导零计数指令的平台特定内在要慢,但便携式ISO C没有这样的功能.有些CPU也没有前导零计数指令,但其中一些可以有效地将整数转换为double.尽管如此(例如,在PowerPC上,它需要存储/重新加载并且通常导致加载命中存储停顿),将FP位模式类型化为整数可能会很慢.
该算法可能对SIMD实现有用,因为较少的CPU具有SIMD lzcnt.x86只能用AVX512CD获得这样的指令
Kaz Kylheku在这里
我对这个超过63位数的两种方法(gcc x86_64上的长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#include #include 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位设置!
在输入0x3FFFFFFFFFFFFFFF上,决策树版本比在1上快得多,并且显示比比特移位器快1120%(12.2倍).
我还将基于GCC内置函数对决策树进行基准测试,并尝试混合输入而不是重复相同的数字.可能会有一些坚持的分支预测正在进行,也许还有一些不切实际的缓存场景,这使得它在重复时人为地加快了速度.
关于什么
int highest_bit(unsigned int a) {
int count;
std::frexp(a, &count);
return count - 1;
}
？
虽然我可能只会使用这种方法,如果我绝对需要最好的性能(例如编写某种涉及位板的棋盘游戏AI),最有效的解决方案是使用内联ASM.有关解释的代码,请参阅此博客文章的"优化"部分.
[...],
bsrl汇编指令计算最高位的位置.因此,我们可以使用这个asm声明:asm ("bsrl %1, %0" : "=r" (position) : "r" (number));
以下是本页目前给出的算法的一些(简单)基准测试......
尚未对unsigned int的所有输入进行测试; 所以在盲目使用之前先检查一下;)
在我的机器上clz(__ builtin_clz)和asm工作得最好.asm似乎比clz更快......但它可能是由于简单的基准...
//////// go.c /////////////////////////////// // compile with: gcc go.c -o go -lm #include#include #include #include /***************** math ********************/ #define POS_OF_HIGHESTBITmath(a) /* 0th position is the Least-Signif-Bit */ \ ((unsigned) log2(a)) /* thus: do not use if a <= 0 */ #define NUM_OF_HIGHESTBITmath(a) ((a) \ ? (1U << POS_OF_HIGHESTBITmath(a)) \ : 0) /***************** clz ********************/ unsigned NUM_BITS_U = ((sizeof(unsigned) << 3) - 1); #define POS_OF_HIGHESTBITclz(a) (NUM_BITS_U - __builtin_clz(a)) /* only works for a != 0 */ #define NUM_OF_HIGHESTBITclz(a) ((a) \ ? (1U << POS_OF_HIGHESTBITclz(a)) \ : 0) /***************** i2f ********************/ double FF; #define POS_OF_HIGHESTBITi2f(a) (FF = (double)(ui|1), ((*(1+(unsigned*)&FF))>>20)-1023) #define NUM_OF_HIGHESTBITi2f(a) ((a) \ ? (1U << POS_OF_HIGHESTBITi2f(a)) \ : 0) /***************** asm ********************/ unsigned OUT; #define POS_OF_HIGHESTBITasm(a) (({asm("bsrl %1,%0" : "=r"(OUT) : "r"(a));}), OUT) #define NUM_OF_HIGHESTBITasm(a) ((a) \ ? (1U << POS_OF_HIGHESTBITasm(a)) \ : 0) /***************** bitshift1 ********************/ #define NUM_OF_HIGHESTBITbitshift1(a) (({ \ OUT = a; \ OUT |= (OUT >> 1); \ OUT |= (OUT >> 2); \ OUT |= (OUT >> 4); \ OUT |= (OUT >> 8); \ OUT |= (OUT >> 16); \ }), (OUT & ~(OUT >> 1))) \ /***************** bitshift2 ********************/ 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}; #define POS_OF_HIGHESTBITbitshift2(a) (({ \ OUT = a; \ OUT |= OUT >> 1; \ OUT |= OUT >> 2; \ OUT |= OUT >> 4; \ OUT |= OUT >> 8; \ OUT |= OUT >> 16; \ OUT = (OUT >> 1) + 1; \ }), POS[(OUT * 0x077CB531UL) >> 27]) #define NUM_OF_HIGHESTBITbitshift2(a) ((a) \ ? (1U << POS_OF_HIGHESTBITbitshift2(a)) \ : 0) #define LOOPS 100000000U int main() { time_t start, end; unsigned ui; unsigned n; /********* Checking the first few unsigned values (you'll need to check all if you want to use an algorithm here) **************/ printf("math\n"); for (ui = 0U; ui < 18; ++ui) printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITmath(ui)); printf("\n\n"); printf("clz\n"); for (ui = 0U; ui < 18U; ++ui) printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITclz(ui)); printf("\n\n"); printf("i2f\n"); for (ui = 0U; ui < 18U; ++ui) printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITi2f(ui)); printf("\n\n"); printf("asm\n"); for (ui = 0U; ui < 18U; ++ui) { printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITasm(ui)); } printf("\n\n"); printf("bitshift1\n"); for (ui = 0U; ui < 18U; ++ui) { printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITbitshift1(ui)); } printf("\n\n"); printf("bitshift2\n"); for (ui = 0U; ui < 18U; ++ui) { printf("%i\t%i\n", ui, NUM_OF_HIGHESTBITbitshift2(ui)); } printf("\n\nPlease wait...\n\n"); /************************* Simple clock() benchmark ******************/ start = clock(); for (ui = 0; ui < LOOPS; ++ui) n = NUM_OF_HIGHESTBITmath(ui); end = clock(); printf("math:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC); start = clock(); for (ui = 0; ui < LOOPS; ++ui) n = NUM_OF_HIGHESTBITclz(ui); end = clock(); printf("clz:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC); start = clock(); for (ui = 0; ui < LOOPS; ++ui) n = NUM_OF_HIGHESTBITi2f(ui); end = clock(); printf("i2f:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC); start = clock(); for (ui = 0; ui < LOOPS; ++ui) n = NUM_OF_HIGHESTBITasm(ui); end = clock(); printf("asm:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC); start = clock(); for (ui = 0; ui < LOOPS; ++ui) n = NUM_OF_HIGHESTBITbitshift1(ui); end = clock(); printf("bitshift1:\t%e\n", (double)(end-start)/CLOCKS_PER_SEC); start = clock(); for (ui = 0; ui < LOOPS; ++ui) n = NUM_OF_HIGHESTBITbitshift2(ui); end = clock(); printf("bitshift2\t%e\n", (double)(end-start)/CLOCKS_PER_SEC); printf("\nThe lower, the better. Take note that a negative exponent is good! ;)\n"); return EXIT_SUCCESS; }
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指令更快,它在线性时间内运行.这是对数时间.
来自http://aggregate.org/MAGIC/#Most%20Significant%201%20Bit
京公网安备 11010802040832号 | 京ICP备19059560号-6 