在 C 语言中，找到整数中最高集位(msb)的最快/最有效的方法是什么？

虽然我可能只会使用这种方法，如果我绝对需要最好的性能(例如写一些棋盘游戏 AI 涉及位板) ，最有效的解决方案是使用内联 ASM。有关代码的说明，请参阅 这篇博文的优化部分。

[ ... ] ，bsrl汇编指令计算最重要位的位置。因此，我们可以使用这个 asm语句:

asm ("bsrl %1, %0"
: "=r" (position)
: "r" (number));

这有点像查找一种整数日志。有一些小把戏，但是我已经为此制作了我自己的工具。目标当然是速度。

我的实现是，CPU 已经有一个自动位检测器，用于整数浮点转换。

double ff=(double)(v|1);
return ((*(1+(uint32_t *)&ff))>>20)-1023;  // assumes x86 endianness

这个版本将值强制转换为双精度值，然后读取指数，这将告诉您位的位置。奇妙的移位和减法是从 IEEE 值中提取适当的部分。

使用 float 稍微快一些，但是 float 只能给出前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 实现非常有用，因为具有 SIMD lzcnt的 CPU 较少。X86只有这样的指令 和 AVX512CD

想想按位运算符。

我第一次没有理解这个问题。您应该生成一个设置了最左边位(其他为零)的 int。假设 cmp 设置为该值:

position = sizeof(int)*8
while(!(n & cmp)){
n <<=1;
position--;
}

假设你在 x86上玩一会儿内联汇编，英特尔提供了一个 BSR指令(“位扫描反向”)。它是 一些 x86s 上的 很快(在其他机器上进行微编码)。手册上说:

在源操作数中搜索最有意义的集合 位(1位)。如果最重要的1 找到位，则存储其位索引 在目标操作数中。源操作数可以是 寄存器或内存位置; 目标操作数是一个寄存器 位索引是从 源操作数的位0。如果 内容源操作数为0，则 目标操作数的内容为 未定义。

(如果你在 PowerPC 上，有一个类似的 cntlz(“计数前导零”)指令。)

Gcc 的示例代码:

#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节)它比循环代码快得多。

这应该是闪电般的速度:

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];
}

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));
}

一个寄存器，十三条指令。信不信由你，这通常比上面提到的 BSR 指令更快，因为它是线性时间运行的。这是对数时间。

来自 http://aggregate.org/MAGIC/#Most%20Significant%201%20Bit

海湾合作委员会有以下说明:

 -- 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'.

(“未定义的结果”不是 C 未定义行为，只是一个未定义的值。它实际上是指令运行时目标寄存器中的内容。AMD 记录了这一点，而英特尔没有，但英特尔的 CPU 确实实现了这一行为。但是它是 没有，不管你之前给 C 变量赋值的是什么，当 gcc 把 C 转换成 asm 时，通常不是这样运行的。另见 为什么打破 LZCNT 的“输出依赖性”很重要？)

由于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位值正确工作。

这里有一些(简单的)基准，算法目前在这一页..。

这些算法还没有在所有无符号整型输入上进行过测试; 因此，在盲目使用某些东西之前，首先要检查一下;)

在我的机器上工作得最好。高潮看起来甚至比 clz 还快... 但这可能是由于简单的基准..。

//////// 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;
}

扩展乔什的基准。 一个人可以如下改进班级

/***************** clz2 ********************/


#define NUM_OF_HIGHESTBITclz2(a) ((a)                              \
? (((1U) << (sizeof(unsigned)*8-1)) >> __builtin_clz(a)) \
: 0)

关于 asm: 请注意存在 bsr 和 bsrl (这是“ long”版本)。普通的可能会快一点。

我需要一个例行程序来做到这一点，在搜索网页(并找到这个页面)之前，我想出了自己的解决方案，基于二进制搜索。虽然我相信以前有人这么做过！它运行在恒定的时间，可以比“显而易见”的解决方案张贴更快，虽然我没有作出任何伟大的主张，只是张贴感兴趣。

int highest_bit(unsigned int a) {
static const unsigned int maskv[] = { 0xffff, 0xff, 0xf, 0x3, 0x1 };
const unsigned int *mask = maskv;
int l, h;


if (a == 0) return -1;


l = 0;
h = 32;


do {
int m = l + (h - l) / 2;


if ((a >> m) != 0) l = m;
else if ((a & (*mask << l)) != 0) h = m;


mask++;
} while (l < h - 1);


return l;
}

我是 Kaz Kylheku

我为这个超过63位数字(gcc x86 _ 64上的长长类型)测试了两种方法，远离符号位。

(你知道，我碰巧需要这个“寻找最高位”。)

我实现了数据驱动的二进制搜索(基于上面的一个答案)。我还手工实现了一个完全展开的决策树，它只是带有直接操作数的代码。没有循环，没有桌子。

除了二进制搜索有一个显式测试的 n = 0情况外，决策树(最高 _ bit _ unroll)的基准测试速度快了69% 。

二进制搜索对于0的特殊测试只比没有特殊测试的决策树快48% 。

编译器，机器: (GCC 4.5.2,-O3，x86-64,2867Mhz 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位的！

在输入0x3FFFFFFFFFFFFFFFFF 上，决策树版本比在1上快得多，并且显示比位移位器快1120% (12.2倍)。

我还将针对 GCC 内置函数对决策树进行基准测试，并尝试混合输入，而不是针对相同的数字重复。可能存在一些粘连分支预测，也可能存在一些不切实际的缓存场景，使其在重复时人为地提高速度。

把这个放进去，因为它是“另一个”方法，似乎与其他已经给出的方法不同。

如果返回 x==0，则返回 -1，否则返回 floor( log2(x))(最大结果31)

将问题从32位减少到4位，然后使用表。也许不够优雅，但是很实用。

这是我在因为可移植性问题而不想使用 __builtin_clz时所使用的。

为了使它更紧凑，可以使用循环来减少，每次增加4到 r，最多7次迭代。或者一些混合，比如(对于64位) : 循环减少到8，测试减少到4。

int log2floor( unsigned x ){
static const signed char wtab[16] = {-1,0,1,1, 2,2,2,2, 3,3,3,3,3,3,3,3};
int r = 0;
unsigned xk = x >> 16;
if( xk != 0 ){
r = 16;
x = xk;
}
// x is 0 .. 0xFFFF
xk = x >> 8;
if( xk != 0){
r += 8;
x = xk;
}
// x is 0 .. 0xFF
xk = x >> 4;
if( xk != 0){
r += 4;
x = xk;
}
// now x is 0..15; x=0 only if originally zero.
return r + wtab[x];
}

关于什么

int highest_bit(unsigned int a) {
int count;
std::frexp(a, &count);
return count - 1;
}

？

正如上面的答案所指出的，有很多方法可以确定最重要的位。然而，正如我们所指出的，这些方法对于32位或64位寄存器来说可能是唯一的。< strong > stanford.edu bithacks page 提供了同时适用于32位和64位计算的解决方案。只需要做一点工作，就可以将它们组合起来，提供一种可靠的跨体系结构方法来获得 MSB。我在64位和32位计算机上编译和工作的解决方案是:

#if defined(__LP64__) || defined(_LP64)
# define BUILD_64   1
#endif


#include <stdio.h>
#include <stdint.h>  /* for uint32_t */


/* CHAR_BIT  (or include limits.h) */
#ifndef CHAR_BIT
#define CHAR_BIT  8
#endif  /* CHAR_BIT */


/*
* Find the log base 2 of an integer with the MSB N set in O(N)
* operations. (on 64bit & 32bit architectures)
*/
int
getmsb (uint32_t word)
{
int r = 0;
if (word < 1)
return 0;
#ifdef BUILD_64
union { uint32_t u[2]; double d; } t;  // temp
t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] = 0x43300000;
t.u[__FLOAT_WORD_ORDER!=LITTLE_ENDIAN] = word;
t.d -= 4503599627370496.0;
r = (t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] >> 20) - 0x3FF;
#else
while (word >>= 1)
{
r++;
}
#endif  /* BUILD_64 */
return r;
}

使用逐次逼近的 C 语言版本:

unsigned int getMsb(unsigned int n)
{
unsigned int msb  = sizeof(n) * 4;
unsigned int step = msb;
while (step > 1)
{
step /=2;
if (n>>msb)
msb += step;
else
msb -= step;
}
if (n>>msb)
msb++;
return (msb - 1);
}

优点: 不管提供的数字是多少，运行时间都是常数，因为循环的数目总是相同的。 (使用“ unsignedint”时循环4次)

C99 给了我们 log2。这就消除了您在本页看到的所有特殊的 log2实现的需要。您可以像下面这样使用标准的 log2实现:

const auto n = 13UL;
const auto Index = (unsigned long)log2(n);


printf("MSB is: %u\n", Index); // Prints 3 (zero offset)

0UL的 n也需要防范，因为:

返回 -∞并引发 FE _ DIVBYZERO

我已经用这个检查编写了一个例子，在这里任意地将 Index设置为 ULONG_MAX: https://ideone.com/u26vsi

恶性病毒的 GCC 唯一答案的必然结果是:

const auto n = 13UL;
unsigned long Index;


_BitScanReverse(&Index, n);
printf("MSB is: %u\n", Index); // Prints 3 (zero offset)

_BitScanReverse 的文档指出，Index是:

用所找到的第一设置位(1)的位位置加载

在实践中，我发现如果 n是 0UL那就是 ABC2设置为 0UL，就像 n是 1UL一样。但在 0UL的 n的情况下，文档中唯一保证的是返回值是:

如果没有找到设置位，则为0

因此，类似于返回值上面的 log2实现，在这种情况下，应该检查将 Index设置为标记的值。我在这里再次编写了一个使用 ULONG_MAX作为标志值的示例: http://rextester.com/GCU61409

这是某种二进制搜索，它适用于所有类型的(无符号!)整数类型

#include <climits>
#define UINT (unsigned int)
#define UINT_BIT (CHAR_BIT*sizeof(UINT))


int msb(UINT x)
{
if(0 == x)
return -1;


int c = 0;


for(UINT i=UINT_BIT>>1; 0<i; i>>=1)
if(static_cast<UINT>(x >> i))
{
x >>= i;
c |= i;
}


return c;
}

使完整:

#include <climits>
#define UINT unsigned int
#define UINT_BIT (CHAR_BIT*sizeof(UINT))


int lsb(UINT x)
{
if(0 == x)
return -1;


int c = UINT_BIT-1;


for(UINT i=UINT_BIT>>1; 0<i; i>>=1)
if(static_cast<UINT>(x << i))
{
x <<= i;
c ^= i;
}


return c;
}

密码:

    // x>=1;
unsigned func(unsigned x) {
double d = x ;
int p= (*reinterpret_cast<long long*>(&d) >> 52) - 1023;
printf( "The left-most non zero bit of %d is bit %d\n", x, p);
}

或者通过设置 Y = 1得到 FPU 指令 FYL2X (Y * Log2X)的整数部分

注意，您要做的是计算一个整数的整数 log2,

#include <stdio.h>
#include <stdlib.h>


unsigned int
Log2(unsigned long x)
{
unsigned long n = x;
int bits = sizeof(x)*8;
int step = 1; int k=0;
for( step = 1; step < bits; ) {
n |= (n >> step);
step *= 2; ++k;
}
//printf("%ld %ld\n",x, (x - (n >> 1)) );
return(x - (n >> 1));
}

请注意，您可以尝试一次搜索多于1位的内容。

unsigned int
Log2_a(unsigned long x)
{
unsigned long n = x;
int bits = sizeof(x)*8;
int step = 1;
int step2 = 0;
//observe that you can move 8 bits at a time, and there is a pattern...
//if( x>1<<step2+8 ) { step2+=8;
//if( x>1<<step2+8 ) { step2+=8;
//if( x>1<<step2+8 ) { step2+=8;
//}
//}
//}
for( step2=0; x>1L<<step2+8; ) {
step2+=8;
}
//printf("step2 %d\n",step2);
for( step = 0; x>1L<<(step+step2); ) {
step+=1;
//printf("step %d\n",step+step2);
}
printf("log2(%ld) %d\n",x,step+step2);
return(step+step2);
}

这种方法使用二进制搜索

unsigned int
Log2_b(unsigned long x)
{
unsigned long n = x;
unsigned int bits = sizeof(x)*8;
unsigned int hbit = bits-1;
unsigned int lbit = 0;
unsigned long guess = bits/2;
int found = 0;


while ( hbit-lbit>1 ) {
//printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
//when value between guess..lbit
if( (x<=(1L<<guess)) ) {
//printf("%ld < 1<<%d %ld\n",x,guess,1L<<guess);
hbit=guess;
guess=(hbit+lbit)/2;
//printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
}
//when value between hbit..guess
//else
if( (x>(1L<<guess)) ) {
//printf("%ld > 1<<%d %ld\n",x,guess,1L<<guess);
lbit=guess;
guess=(hbit+lbit)/2;
//printf("log2(%ld) %d<%d<%d\n",x,lbit,guess,hbit);
}
}
if( (x>(1L<<guess)) ) ++guess;
printf("log2(x%ld)=r%d\n",x,guess);
return(guess);
}

另一个二分法也许更易读,

unsigned int
Log2_c(unsigned long x)
{
unsigned long v = x;
unsigned int bits = sizeof(x)*8;
unsigned int step = bits;
unsigned int res = 0;
for( step = bits/2; step>0; )
{
//printf("log2(%ld) v %d >> step %d = %ld\n",x,v,step,v>>step);
while ( v>>step ) {
v>>=step;
res+=step;
//printf("log2(%ld) step %d res %d v>>step %ld\n",x,step,res,v);
}
step /= 2;
}
if( (x>(1L<<res)) ) ++res;
printf("log2(x%ld)=r%ld\n",x,res);
return(res);
}

因为你想测试这些,

int main()
{
unsigned long int x = 3;
for( x=2; x<1000000000; x*=2 ) {
//printf("x %ld, x+1 %ld, log2(x+1) %d\n",x,x+1,Log2(x+1));
printf("x %ld, x+1 %ld, log2_a(x+1) %d\n",x,x+1,Log2_a(x+1));
printf("x %ld, x+1 %ld, log2_b(x+1) %d\n",x,x+1,Log2_b(x+1));
printf("x %ld, x+1 %ld, log2_c(x+1) %d\n",x,x+1,Log2_c(x+1));
}
return(0);
}

一些过于复杂的答案。只有当输入已经是2的幂时，才应该使用 Debruin 技术，否则会有更好的方法。对于2的输入功率，Debruin 是绝对最快的，甚至比我测试过的任何处理器上的 _BitScanReverse都要快。但是，在一般情况下，_BitScanReverse(或者在编译器中调用的任何内部函数)是最快的(在某些 CPU 上可以对它进行微编码)。

如果内部函数不是一个选项，这里有一个处理一般输入的最优软件解决方案。

u8  inline log2 (u32 val)  {
u8  k = 0;
if (val > 0x0000FFFFu) { val >>= 16; k  = 16; }
if (val > 0x000000FFu) { val >>= 8;  k |= 8;  }
if (val > 0x0000000Fu) { val >>= 4;  k |= 4;  }
if (val > 0x00000003u) { val >>= 2;  k |= 2;  }
k |= (val & 2) >> 1;
return k;
}

请注意，这个版本不需要在最后查找德布鲁因，不像其他大多数答案。它计算位置。

但是，如果多次调用表，则表可能更可取，因为表的加速会使缓存丢失的风险相形见绌。

u8 kTableLog2[256] = {
0,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7
};


u8 log2_table(u32 val)  {
u8  k = 0;
if (val > 0x0000FFFFuL) { val >>= 16; k  = 16; }
if (val > 0x000000FFuL) { val >>=  8; k |=  8; }
k |= kTableLog2[val]; // precompute the Log2 of the low byte


return k;
}

这将产生这里给出的所有软件答案中最高的吞吐量，但是如果您只是偶尔调用它，那么更喜欢像我的第一个代码片段那样的无表解决方案。

我知道这个问题很老了但是我刚刚实现了一个 Msb ()函数, 我发现这里和其他网站上提供的大多数解决方案并不一定是最有效的——至少就我个人对效率的定义而言是如此(参见下面的 < em > 更新 )。原因如下:

大多数解决方案(尤其是那些使用某种二进制搜索方案或者从右到左进行线性扫描的天真方法)似乎忽略了这样一个事实: 对于任意的二进制数，没有多少是以很长的零序列开始的。实际上，对于任何位宽，一半的整数以 1开头，四分之一以 01开头。 明白我的意思了吗？我的观点是，从最有意义位开始到最不有意义位(从左到右)的 线性扫描线性扫描并不像乍看上去那么“线性”。

可以显示 ¹，对于任意位宽度，需要测试的平均位数最多为2。这转化为 分期付款时间复杂度相对于 < em > O (1) 的位数(!).

当然，最糟糕的情况仍然是 < em > O (n) ，比二进制搜索方法得到的 < em > O (log (n)) 更糟糕，但是因为最糟糕的情况很少，所以对于大多数应用程序来说可以忽略不计(< em > 更新 : 不完全是: 可能很少，但是它们可能发生的概率很高——参见下面的 < em > 更新 )。

这是我想出来的“天真”的方法，至少在我的机器上打败了大多数其他方法(对于32位 int 的二进制搜索方案总是需要 木头₂(32) = 5个步骤，而这个愚蠢的算法平均需要不到2个步骤)——抱歉这是 C + + 而不是纯 C:

template <typename T>
auto msb(T n) -> int
{
static_assert(std::is_integral<T>::value && !std::is_signed<T>::value,
"msb<T>(): T must be an unsigned integral type.");


for (T i = std::numeric_limits<T>::digits - 1, mask = 1 << i; i >= 0; --i, mask >>= 1)
{
if ((n & mask) != 0)
return i;
}


return 0;
}

更新 : 虽然我在这里写的对于 随心所欲整数来说是完全正确的，其中每个位的组合都是同样可能的(我的速度测试只是测量了确定 所有32位整数的最小二乘法需要多长时间) ，但对于实际生活中的整数，这样一个函数将被调用，通常遵循不同的模式: 例如，在我的代码中，这个函数是用来确定一个 物体大小是一个2的幂，或者找出下一个大于或等于一个 物体大小的2的幂。 我的猜测是，大多数使用 MSB 的应用程序涉及的数字远小于一个整数可以表示的最大数字(对象大小很少利用 Size _ t中的所有位)。在这种情况下，我的解决方案实际上比二进制搜索方法执行得更差——因此后者可能更可取，即使我的解决方案在遍历 所有整数时更快。
TL; DR: 现实生活中的整数可能会偏向于这个简单算法的最坏情况，这会使它最终的性能变差——尽管对于真正的任意整数来说它是 分期付款 < em > O (1) 。

^{论点是这样的(草稿) : 设 [俄语]为位数(位宽)。总共有一个 2 < sup > n} 整数可以用 [俄语]位来表示。有以 1开始的 2 < sup > n-1 整数(第一个 1是固定的，其余的 N-1位可以是任何东西)。这些整数只需要循环的一次交替就可以确定 MSB。此外，还有以 01开头的 2 < sup > n-2 整数，需要2次迭代，以 2 < sup > n 0开头的 2 < sup > n-3 整数，需要3次迭代，等等。

如果我们把所有可能的整数的所有迭代次数相加，然后除以 2 < sup > n ，即整数的总数，我们就得到了确定 [俄语]位整数的 MSB 所需的平均迭代次数:

(1 * 2^N-1 + 2 * 2^N-2 + 3 * 2^N-3 + ... + n)/2^N

这一系列的平均迭代实际上是收敛的，并且对于 [俄语]的无穷大极限是2

因此，对于任意数量的比特，从左到右的幼稚算法实际上具有 分期付款常数时间复杂度 < em > O (1) 。

哇，答案真多。我不后悔回答了一个老问题。

int result = 0;//could be a char or int8_t instead
if(value){//this assumes the value is 64bit
if(0xFFFFFFFF00000000&value){  value>>=(1<<5); result|=(1<<5);  }//if it is 32bit then remove this line
if(0x00000000FFFF0000&value){  value>>=(1<<4); result|=(1<<4);  }//and remove the 32msb
if(0x000000000000FF00&value){  value>>=(1<<3); result|=(1<<3);  }
if(0x00000000000000F0&value){  value>>=(1<<2); result|=(1<<2);  }
if(0x000000000000000C&value){  value>>=(1<<1); result|=(1<<1);  }
if(0x0000000000000002&value){  result|=(1<<0);  }
}else{
result=-1;
}

这个答案和另一个答案非常相似... ... 哦，好吧。

另一张海报使用 字节范围查找提供了 查阅表。如果您希望获得更高的性能(代价是32K 内存，而不是仅仅256个查找条目) ，这里有一个使用 15位查找表的解决方案，在 C # 7中用于 .NET。

有趣的部分是初始化表。由于这是一个相对较小的块，我们希望在进程的生命周期中使用它，因此我使用 Marshal.AllocHGlobal为其分配非托管内存。正如您所看到的，为了获得最佳性能，整个示例都是以本机方式编写的:

readonly static byte[] msb_tab_15;


// Initialize a table of 32768 bytes with the bit position (counting from LSB=0)
// of the highest 'set' (non-zero) bit of its corresponding 16-bit index value.
// The table is compressed by half, so use (value >> 1) for indexing.
static MyStaticInit()
{
var p = new byte[0x8000];


for (byte n = 0; n < 16; n++)
for (int c = (1 << n) >> 1, i = 0; i < c; i++)
p[c + i] = n;


msb_tab_15 = p;
}

该表需要通过上面的代码进行一次性初始化。它是只读的，因此可以共享单个全局副本以进行并发访问。使用这个表，您可以快速查找整数 日志 < sub > 2 ，这就是我们在这里要查找的，查找所有不同的整数宽度(8、16、32和64位)。

请注意，0的表条目是唯一的整数，其中没有定义“最高集位”的概念，该表条目的值为 -1。这种区分对于正确处理下面代码中的0值大写单词是必要的。废话不多说，下面是各种整数原语的代码:

乌龙(64位)版本

/// <summary> Index of the highest set bit in 'v', or -1 for value '0' </summary>
public static int HighestOne(this ulong v)
{
if ((long)v <= 0)
return (int)((v >> 57) & 0x40) - 1;      // handles cases v==0 and MSB==63


int j = /**/ (int)((0xFFFFFFFFU - v /****/) >> 58) & 0x20;
j |= /*****/ (int)((0x0000FFFFU - (v >> j)) >> 59) & 0x10;
return j + msb_tab_15[v >> (j + 1)];
}

Uint (32位)版本

/// <summary> Index of the highest set bit in 'v', or -1 for value '0' </summary>
public static int HighestOne(uint v)
{
if ((int)v <= 0)
return (int)((v >> 26) & 0x20) - 1;     // handles cases v==0 and MSB==31


int j = (int)((0x0000FFFFU - v) >> 27) & 0x10;
return j + msb_tab_15[v >> (j + 1)];
}

以上各种过载

public static int HighestOne(long v) => HighestOne((ulong)v);
public static int HighestOne(int v) => HighestOne((uint)v);
public static int HighestOne(ushort v) => msb_tab_15[v >> 1];
public static int HighestOne(short v) => msb_tab_15[(ushort)v >> 1];
public static int HighestOne(char ch) => msb_tab_15[ch >> 1];
public static int HighestOne(sbyte v) => msb_tab_15[(byte)v >> 1];
public static int HighestOne(byte v) => msb_tab_15[v >> 1];

这是一个完整的，工作的解决方案，代表了最好的性能。NET 4.7.2的众多替代品，我将其与专门的性能测试工具进行了比较。其中一些在下面提到。测试参数是所有65位位的均匀密度，即 0... 31/63加值 0(产生结果 -1)。位 下面目标索引位置随机填充。测试只有 X64，发布模式，启用了 JIT 优化。

这是我正式回答的最后一个问题; 下面是一些随意的注释和源代码链接，这些代码是为了验证上述代码的性能和正确性而运行的与测试相关的替代测试候选者提供的。 < hr >

上面提供的编码为 Tab16A 的版本在许多运行中都是一致的赢家。这些不同的候选者，在积极的工作/划伤形式，可以找到 给你，给你和 给你。

 1  candidates.HighestOne_Tab16A               622,496
2  candidates.HighestOne_Tab16C               628,234
3  candidates.HighestOne_Tab8A                649,146
4  candidates.HighestOne_Tab8B                656,847
5  candidates.HighestOne_Tab16B               657,147
6  candidates.HighestOne_Tab16D               659,650
7  _highest_one_bit_UNMANAGED.HighestOne_U    702,900
8  de_Bruijn.IndexOfMSB                       709,672
9  _old_2.HighestOne_Old2                     715,810
10  _test_A.HighestOne8                        757,188
11  _old_1.HighestOne_Old1                     757,925
12  _test_A.HighestOne5  (unsafe)              760,387
13  _test_B.HighestOne8  (unsafe)              763,904
14  _test_A.HighestOne3  (unsafe)              766,433
15  _test_A.HighestOne1  (unsafe)              767,321
16  _test_A.HighestOne4  (unsafe)              771,702
17  _test_B.HighestOne2  (unsafe)              772,136
18  _test_B.HighestOne1  (unsafe)              772,527
19  _test_B.HighestOne3  (unsafe)              774,140
20  _test_A.HighestOne7  (unsafe)              774,581
21  _test_B.HighestOne7  (unsafe)              775,463
22  _test_A.HighestOne2  (unsafe)              776,865
23  candidates.HighestOne_NoTab                777,698
24  _test_B.HighestOne6  (unsafe)              779,481
25  _test_A.HighestOne6  (unsafe)              781,553
26  _test_B.HighestOne4  (unsafe)              785,504
27  _test_B.HighestOne5  (unsafe)              789,797
28  _test_A.HighestOne0  (unsafe)              809,566
29  _test_B.HighestOne0  (unsafe)              814,990
30  _highest_one_bit.HighestOne                824,345
30  _bitarray_ext.RtlFindMostSignificantBit    894,069
31  candidates.HighestOne_Naive                898,865

值得注意的是，ntdll.dll!RtlFindMostSignificantBit通过 P/Invoke 的糟糕表现:

[DllImport("ntdll.dll"), SuppressUnmanagedCodeSecurity, SecuritySafeCritical]
public static extern int RtlFindMostSignificantBit(ulong ul);

这真是太糟糕了，因为这是整个实际的函数:

    RtlFindMostSignificantBit:
bsr rdx, rcx
mov eax,0FFFFFFFFh
movzx ecx, dl
cmovne      eax,ecx
ret

我无法想象源于这五行的糟糕性能，因此管理/本地转换惩罚肯定是罪魁祸首。我还感到惊讶的是，相对于128字节(和256字节)的 byte(8位)查找表，测试真的更青睐32KB (和64KB)的 short(16位)直接查找表。我原以为下面的代码会比16位查找更有竞争力，但是后者的表现一直比这个好:

public static int HighestOne_Tab8A(ulong v)
{
if ((long)v <= 0)
return (int)((v >> 57) & 64) - 1;


int j;
j =  /**/ (int)((0xFFFFFFFFU - v) >> 58) & 32;
j += /**/ (int)((0x0000FFFFU - (v >> j)) >> 59) & 16;
j += /**/ (int)((0x000000FFU - (v >> j)) >> 60) & 8;
return j + msb_tab_8[v >> j];
}

我要指出的最后一件事是，我对 deBruijn 方法没有进展得更好感到非常震惊。这就是我之前普遍使用的方法:

const ulong N_bsf64 = 0x07EDD5E59A4E28C2,
N_bsr64 = 0x03F79D71B4CB0A89;


readonly public static sbyte[]
bsf64 =
{
63,  0, 58,  1, 59, 47, 53,  2, 60, 39, 48, 27, 54, 33, 42,  3,
61, 51, 37, 40, 49, 18, 28, 20, 55, 30, 34, 11, 43, 14, 22,  4,
62, 57, 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21,
56, 45, 25, 31, 35, 16,  9, 12, 44, 24, 15,  8, 23,  7,  6,  5,
},
bsr64 =
{
0, 47,  1, 56, 48, 27,  2, 60, 57, 49, 41, 37, 28, 16,  3, 61,
54, 58, 35, 52, 50, 42, 21, 44, 38, 32, 29, 23, 17, 11,  4, 62,
46, 55, 26, 59, 40, 36, 15, 53, 34, 51, 20, 43, 31, 22, 10, 45,
25, 39, 14, 33, 19, 30,  9, 24, 13, 18,  8, 12,  7,  6,  5, 63,
};


public static int IndexOfLSB(ulong v) =>
v != 0 ? bsf64[((v & (ulong)-(long)v) * N_bsf64) >> 58] : -1;


public static int IndexOfMSB(ulong v)
{
if ((long)v <= 0)
return (int)((v >> 57) & 64) - 1;


v |= v >> 1; v |= v >> 2;  v |= v >> 4;   // does anybody know a better
v |= v >> 8; v |= v >> 16; v |= v >> 32;  // way than these 12 ops?
return bsr64[(v * N_bsr64) >> 58];
}

有很多关于 deBruijn 方法 在这个问题上如何优越和伟大的讨论，我倾向于同意。我的推测是，虽然 deBruijn 和直接查找表方法(我发现是最快的)都必须执行表查找，而且都具有非常小的分支，但是只有 deBruijn 具有64位乘法运算。我只在这里测试了 IndexOfMSB函数——而不是 deBruijn IndexOfLSB——但是我希望后者的机会更大，因为它的操作要少得多(参见上文) ，而且我很可能会继续在 LSB 中使用它。

我假设你的问题是一个整数(下面称为 v) ，而不是一个无符号整数。

int v = 612635685; // whatever value you wish


unsigned int get_msb(int v)
{
int r = 31;                         // maximum number of iteration until integer has been totally left shifted out, considering that first bit is index 0. Also we could use (sizeof(int)) << 3 - 1 instead of 31 to make it work on any platform.


while (!(v & 0x80000000) && r--) {   // mask of the highest bit
v <<= 1;                        // multiply integer by 2.
}
return r;                           // will even return -1 if no bit was set, allowing error catch
}

如果你想让它工作而不考虑符号，你可以在循环之前添加一个额外的“ v < < = 1;”(并相应地将 r 值改为30)。 如果我忘了什么东西，请告诉我。我还没有测试过，但它应该可以正常工作。

我谦卑的方法很简单:

MSB (x) = INT [ Log (x)/Log (2)]

转换: x 的 MSB 是(Log of Base x 除以 Log of Base 2)的整数值。

这可以轻松快速地适应任何编程语言。在你的计算器上试一下，看看它是否有效。

这里有一个 C的快速解决方案，可以在 海湾合作委员会和 当中使用，可以进行复制和粘贴。

#include <limits.h>


unsigned int fls(const unsigned int value)
{
return (unsigned int)1 << ((sizeof(unsigned int) * CHAR_BIT) - __builtin_clz(value) - 1);
}


unsigned long flsl(const unsigned long value)
{
return (unsigned long)1 << ((sizeof(unsigned long) * CHAR_BIT) - __builtin_clzl(value) - 1);
}


unsigned long long flsll(const unsigned long long value)
{
return (unsigned long long)1 << ((sizeof(unsigned long long) * CHAR_BIT) - __builtin_clzll(value) - 1);
}

还有 C + + 的改进版。

#include <climits>


constexpr unsigned int fls(const unsigned int value)
{
return (unsigned int)1 << ((sizeof(unsigned int) * CHAR_BIT) - __builtin_clz(value) - 1);
}


constexpr unsigned long fls(const unsigned long value)
{
return (unsigned long)1 << ((sizeof(unsigned long) * CHAR_BIT) - __builtin_clzl(value) - 1);
}


constexpr unsigned long long fls(const unsigned long long value)
{
return (unsigned long long)1 << ((sizeof(unsigned long long) * CHAR_BIT) - __builtin_clzll(value) - 1);
}

代码假设 value不是 0。如果你想允许0，你需要修改它。

使用 VPTEST (D，W，B)和 PSRLDQ 指令的组合，将焦点集中在包含最重要位的字节上，如下所示，使用 Perl 中的这些指令的模拟，可以在下面找到:

Https://github.com/philiprbrenan/simdavx512

if (1) {                                                                        #TpositionOfMostSignificantBitIn64
my @m = (                                                                     # Test strings
#B0       1       2       3       4       5       6       7
#b0123456701234567012345670123456701234567012345670123456701234567
'0000000000000000000000000000000000000000000000000000000000000000',
'0000000000000000000000000000000000000000000000000000000000000001',
'0000000000000000000000000000000000000000000000000000000000000010',
'0000000000000000000000000000000000000000000000000000000000000111',
'0000000000000000000000000000000000000000000000000000001010010000',
'0000000000000000000000000000000000001000000001100100001010010000',
'0000000000000000000001001000010000000000000001100100001010010000',
'0000000000000000100000000000000100000000000001100100001010010000',
'1000000000000000100000000000000100000000000001100100001010010000',
);
my @n = (0, 1, 2, 3, 10, 28, 43, 48, 64);                                     # Expected positions of msb


sub positionOfMostSignificantBitIn64($)                                       # Find the position of the most significant bit in a string of 64 bits starting from 1 for the least significant bit or return 0 if the input field is all zeros
{my ($s64) = @_;                                                             # String of 64 bits


my $N = 128;                                                                # 128 bit operations
my $f = 0;                                                                  # Position of first bit set
my $x = '0'x$N;                                                             # Double Quad Word set to 0
my $s = substr $x.$s64, -$N;                                                # 128 bit area needed


substr(VPTESTMD($s, $s), -2, 1) eq '1' ? ($s = PSRLDQ $s, 4) : ($f += 32);  # Test 2 dwords
substr(VPTESTMW($s, $s), -2, 1) eq '1' ? ($s = PSRLDQ $s, 2) : ($f += 16);  # Test 2 words
substr(VPTESTMB($s, $s), -2, 1) eq '1' ? ($s = PSRLDQ $s, 1) : ($f +=  8);  # Test 2 bytes


$s = substr($s, -8);                                                        # Last byte remaining


$s < $_ ? ++$f : last for                                                   # Search remaing byte
(qw(10000000 01000000 00100000 00010000
00001000 00000100 00000010 00000001));


64 - $f                                                                     # Position of first bit set
}


ok $n[$_] eq positionOfMostSignificantBitIn64 $m[$_] for keys @m              # Test
}

这看起来很大，但工作真的很快，相比循环感谢从蓝铁匠

int Bit_Find_MSB_Fast(int x2)
{
long x = x2 & 0x0FFFFFFFFl;
long num_even = x & 0xAAAAAAAA;
long num_odds = x & 0x55555555;


if (x == 0) return(0);


if (num_even > num_odds)
{
if ((num_even & 0xFFFF0000) != 0) // top 4
{
if ((num_even & 0xFF000000) != 0)
{
if ((num_even & 0xF0000000) != 0)
{
if ((num_even & 0x80000000) != 0) return(32);
else
return(30);
}
else
{
if ((num_even & 0x08000000) != 0) return(28);
else
return(26);
}
}
else
{
if ((num_even & 0x00F00000) != 0)
{
if ((num_even & 0x00800000) != 0) return(24);
else
return(22);
}
else
{
if ((num_even & 0x00080000) != 0) return(20);
else
return(18);
}
}
}
else
{
if ((num_even & 0x0000FF00) != 0)
{
if ((num_even & 0x0000F000) != 0)
{
if ((num_even & 0x00008000) != 0) return(16);
else
return(14);
}
else
{
if ((num_even & 0x00000800) != 0) return(12);
else
return(10);
}
}
else
{
if ((num_even & 0x000000F0) != 0)
{
if ((num_even & 0x00000080) != 0)return(8);
else
return(6);
}
else
{
if ((num_even & 0x00000008) != 0) return(4);
else
return(2);
}
}
}
}
else
{
if ((num_odds & 0xFFFF0000) != 0) // top 4
{
if ((num_odds & 0xFF000000) != 0)
{
if ((num_odds & 0xF0000000) != 0)
{
if ((num_odds & 0x40000000) != 0) return(31);
else
return(29);
}
else
{
if ((num_odds & 0x04000000) != 0) return(27);
else
return(25);
}
}
else
{
if ((num_odds & 0x00F00000) != 0)
{
if ((num_odds & 0x00400000) != 0) return(23);
else
return(21);
}
else
{
if ((num_odds & 0x00040000) != 0) return(19);
else
return(17);
}
}
}
else
{
if ((num_odds & 0x0000FF00) != 0)
{
if ((num_odds & 0x0000F000) != 0)
{
if ((num_odds & 0x00004000) != 0) return(15);
else
return(13);
}
else
{
if ((num_odds & 0x00000400) != 0) return(11);
else
return(9);
}
}
else
{
if ((num_odds & 0x000000F0) != 0)
{
if ((num_odds & 0x00000040) != 0)return(7);
else
return(5);
}
else
{
if ((num_odds & 0x00000004) != 0) return(3);
else
return(1);
}
}
}
}
}

有人建议在 C 语言中添加位操作函数，特别是前导零有助于查找最高位集。参见 http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2827.htm#design-bit-leading.trailing.zeroes.ones

它们被期望在可能的情况下作为内置实现，因此确信这是一种有效的方法。

这类似于最近添加到 C + + (std::countl_zero等)中的内容。

因为我似乎没有其他事情可做，所以我在周末花了大量的时间来解决这个问题。

如果没有直接的硬件支持，那么在 w = 64位的情况下应该可以比 O (log (w))做得更好。实际上，在 O (log log w)中也可以这样做，只不过性能交叉要到 w > = 256位才会发生。

不管怎样，我尝试了一下，我能想到的最好的办法就是下面这些技巧的组合:

uint64_t msb64 (uint64_t n) {


const uint64_t  M1 = 0x1111111111111111;


// we need to clear blocks of b=4 bits: log(w/b) >= b
n |= (n>>1); n |= (n>>2);


// reverse prefix scan, compiles to 1 mulx
uint64_t s = ((M1<<4)*(__uint128_t)(n&M1))>>64;


// parallel-reduce each block
s |= (s>>1);    s |= (s>>2);


// parallel reduce, 1 imul
uint64_t c = (s&M1)*(M1<<4);


// collect last nibble, generate compute count - count%4
c = c >> (64-4-2); // move last nibble to lowest bits leaving two extra bits
c &= (0x0F<<2);    // zero the lowest 2 bits


// add the missing bits; this could be better solved with a bit of foresight
// by having the sum already stored
uint8_t b = (n >> c); // & 0x0F; // no need to zero the bits over the msb


const uint64_t  S = 0x3333333322221100; // last should give -1ul
return c | ((S>>(4*b)) & 0x03);
}

此解决方案是无分支的，并且不需要可以生成缓存丢失的外部表。在现代的 x86-64体系结构中，两个64位乘法器的性能问题不大。

我对这里和其他地方提供的一些最常见解决方案的64位版本进行了基准测试。 事实证明，找到一个一致的时机和排名比我预想的要难得多。这不仅与输入的分布有关，还与乱序执行和其他的 CPU 骗局有关，这些骗局有时会在一个循环中重叠两个或两个以上的计算周期。

我使用 RDTSC 在 AMD Zen 上运行了测试，并采取了一些预防措施，比如运行热身、引入人工链依赖等等。

对于64位伪随机均匀分布，结果如下:

转换为 double 总是令人惊讶地接近内在的本质。一次添加一个比特的“显而易见”的方法在性能上具有最大的扩展，可以与小数字的最快方法相媲美，而对于最大的方法则要慢20倍。

我的方法比 deBrujin 慢50% 左右，但具有不使用额外内存和具有可预测性能的优点。如果有时间的话，我可能会进一步优化它。