n，我想知道最高有效位的位置（即，如果最低有效位在右边，则我想知道最左边是一个1的位的位置），那么找出最快/最有效的方法是什么？<strings.h>中支持ffs()方法来查找第一个设置位，但似乎没有相应的fls()方法。GCC提供以下内置函数:
-- 内置函数: int __builtin_clz (unsigned int x)
返回X从最高位开始的前导0的个数。如果X为0，则结果未定义。
-- 内置函数: int __builtin_clzl (unsigned long)
类似于`__builtin_clz'，不同之处在于参数类型是`unsigned long'。
-- 内置函数: int __builtin_clzll (unsigned long long)
类似于`__builtin_clz'，不同之处在于参数类型是`unsigned long long'。
期望这些内置函数在当前平台上能够高效运行，无论是使用那些复杂的二进制算法还是单条指令。
如果输入可以为零，一个有用的技巧是使用__builtin_clz(x | 1)：将低位设置为1而不修改其他位，使得x=0时输出为31，对于其他任何输入都不会改变输出。
为了避免需要使用这种技巧，你的另一个选择是使用特定于平台的内部函数，例如ARM GCC的__clz（无需头文件）或x86支持lzcnt指令的CPU上的_lzcnt_u32。（请注意，lzcnt在旧的CPU上解码为bsr而不是错误，这会导致非零输入的输出为31-lzcnt。）
不幸的是，在不同于x86平台上，无法使用可移植的方法利用将输入为0时结果定义为32或64(根据操作数宽度)的各种CLZ指令。x86的lzcnt也是如此，而bsr会产生一个位索引，除非你使用31-__builtin_clz(x)，否则编译器会翻转它。
“未定义结果”并不是C未定义行为，它只是一个没有定义的值。实际上，它是指令运行时目标寄存器中的任何内容。AMD记录了这一点，Intel没有，但是Intel的CPU确实实现了这种行为。但它不是你要分配的C变量中先前的内容，这通常不是gcc将C转换为汇编代码的工作方式。请参见为什么破坏LZCNT的“输出依赖性”很重要？
__builtin_ctz 的优势超过了 ffs，后者编译为 BSF 和 CMOV 来处理输入为零的情况。在没有足够短的实现（例如没有 clz 指令的旧 ARM）的体系结构上，gcc 会发出对 libgcc 助手函数的调用。 - Peter Cordes__clz实际上没有头文件可用。此外，在我的CMSIS副本中（应该是相当当前的版本），__CLZ被定义为GCC的__builting_gcc，具有所有这些缺点。有关完整讨论，请参见此问题 - 显然，这样做是为了允许更好的优化，即使它有缺点。 - jaskij由于2的N次方是只有第N位设置为1的整数（1 << N），因此找到最高位设置为1的位置（N）就是该整数的以2为底的整数对数。
http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious
unsigned int v;
unsigned r = 0;
while (v >>= 1) {
r++;
}
这个“显而易见”的算法可能不是对每个人都透明的，但当你意识到代码反复向右移动一位，直到最左边的位被移出（注意C把任何非零值视为true），并返回移动的次数时，它就很容易理解了。这也意味着即使设置了多个位，它也可以工作 - 结果始终针对最高有效位。
如果您在该页面上滚动，会发现更快、更复杂的变体。然而，如果您知道自己正在处理很多前导零的数字，则朴素方法可能提供可接受的速度，因为在C中进行位移相当快，而简单的算法不需要索引数组。
注意：在使用64位值时，对于过于聪明的算法要非常小心；其中许多只对32位值有效。
BSR指令（“位扫描反转”）。它在某些x86上快速执行（在其他处理器上微码化）。根据手册：
（如果您使用PowerPC，则有类似的`cntlz`（“倒数第二个零的位置”）指令。）搜索源操作数以找到最高位的1位。如果找到最高位的1，则将其位索引存储在目标操作数中。源操作数可以是寄存器或存储器位置；目标操作数是寄存器。位索引是从源操作数的第0位开始的无符号偏移量。如果源操作数内容为0，则目标操作数的内容未定义。
#include <iostream>
int 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节）它比循环代码快得多。
__builtin_clz（或__builtin_clzll），它具有相同的未定义行为，可以将其编译为x86上的单个BSR。或者如果可用，则使用LZCNT，因为它在更多CPU上更快（例如，在AMD上即使BSR很慢，LZCNT也很快，可能是因为BSR具有根据输入而不是结果设置ZF的奇怪行为）。或者无论目标架构如何最优，因为它不仅限于x86。无论如何，https://gcc.gnu.org/wiki/DontUseInlineAsm，当您可以避免使用时，因为它会破坏常量传播和一些其他优化。 - Peter Cordes这有点像查找整数对数。虽然有一些位操作技巧，但我已经为此制作了自己的工具。当然目标是速度。
我的想法是CPU已经有一个自动位检测器，用于整数到浮点数的转换！所以可以利用它。
double ff=(double)(v|1);
return ((*(1+(uint32_t *)&ff))>>20)-1023; // assumes x86 endianness
这个版本将值转换为双精度数，然后读取指数，这告诉您位在哪里。这种花式移位和减法是从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及其后版本中，使用union {double d; uint32_t u[2];};。但请注意，在C++中，联合体类型的玩弄只受到一些编译器的扩展支持，而不是ISO C++。
这通常比特定平台的前导零计数指令要慢，但便携式ISO C没有这样的函数。一些CPU也缺乏前导零计数指令，但其中一些可以有效地将整数转换为double。然而，将FP位模式重新解释为整数可能会很慢（例如，在PowerPC上，它需要一个存储/重新加载并且通常会导致负载命中存储延迟）。
这个算法在SIMD实现中可能会有用，因为较少的CPU具有SIMD lzcnt。x86只有在AVX512CD中才有这样的指令。链接
这应该非常快：
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];
}
我是Kaz Kylheku。
我对寻找63位数字（gcc x86_64上的long long类型）中最高位的两种方法进行了基准测试，避开了符号位。（我碰巧需要这个“查找最高位”，你懂的。）
我实现了数据驱动的二分查找（紧密地基于上面的一个答案）。我还手写了一个完全展开的决策树，它只是具有立即操作数的代码。没有循环，没有表格。
除n = 0的情况外，决策树（highest_bit_unrolled）的性能测试比二分查找快69%。
二分查找对于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位！
对于输入0x3FFFFFFFFFFFFFFF，决策树版本比输入1快得多，表现出1120％（12.2倍）的速度优势。
我还将针对GCC内置函数进行决策树测试，也会尝试使用混合输入而不是反复针对同一个数字进行测试。可能存在粘滞分支预测和一些不太真实的缓存情况，这使得它在重复测试时表现得更快。
[...]，
bsrl汇编指令可以计算最高位的位置。因此，我们可以使用这个asm语句：asm ("bsrl %1, %0" : "=r" (position) : "r" (number));
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指令更快，它是对数时间。
-march=native启用它，gcc将用于__builtin_clz(因为它在支持它的每个CPU上都很快)。 即使在像AMD Bulldozer系列这样的CPU上，BSR也不是“慢”的：7个m-op，4个周期延迟和每4个周期吞吐量一个。 在Atom上，BSR非常缓慢：16个周期。 在Silvermont上，它是10个uops和10个周期延迟。 这可能比Silvermont上的BSR的延迟略低，但我不确定。 - Peter Cordes关于什么
int highest_bit(unsigned int a) {
int count;
std::frexp(a, &count);
return count - 1;
}
?
//////// go.c ///////////////////////////////
// compile with: gcc go.c -o go -lm
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/***************** 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;
}