如果我有一些整数 n，并且我想知道最高有效位的位置（也就是说，如果最低有效位在右边，我想知道最左边的位是 1 的位置），找出最快/最有效的方法是什么？
我知道 POSIX 支持ffs()在 strings.h 中找到第一个设置位的方法，但似乎没有相应的fls()方法。
是否有一些我想念的非常明显的方法？
如果您不能使用 POSIX 函数来实现可移植性，那该怎么办？
编辑：一个适用于 32 位和 64 位架构的解决方案怎么样（许多代码清单似乎只适用于 32 位整数）。
Zxaos
问问题
160380 次
30 回答
78
海合会有：
-- 内置函数：int __builtin_clz (unsigned int x)
返回 X 中前导 0 位的数量，从最多开始
重要位的位置。如果 X 为 0，则结果未定义。
-- 内置函数：int __builtin_clzl (unsigned long)
类似于`__builtin_clz'，除了参数类型是`unsigned
长'。
-- 内置函数：int __builtin_clzll (unsigned long long)
类似于`__builtin_clz'，除了参数类型是`unsigned
长长'。
我希望它们被翻译成对您当前平台相当有效的东西，无论是那些花哨的位旋转算法之一，还是一条指令。
如果您的输入可以为零，则一个有用的技巧是__builtin_clz(x | 1)：无条件地设置低位而不修改任何其他使输出31为x=0，而不更改任何其他输入的输出。
为避免需要这样做，您的另一个选择是特定于平台的内在函数，如 ARM GCC __clz（不需要标头）或_lzcnt_u32支持该lzcnt指令的 CPU 上的 x86。（请注意，在较旧的 CPU 上lzcnt解码bsr而不是故障，这会为非零输入提供 31-lzcnt。）
不幸的是，没有办法可移植地利用非 x86 平台上的各种 CLZ 指令，这些指令确实将 input=0 的结果定义为 32 或 64（根据操作数宽度）。x86lzcnt也这样做，同时bsr生成一个位索引，除非您使用31-__builtin_clz(x).
（“未定义的结果”不是 C 未定义的行为，只是一个未定义的值。它实际上是指令运行时目标寄存器中的任何内容。AMD 记录了这一点，英特尔没有，但英特尔的 CPU 确实实现了这种行为。但它不是您分配给的 C 变量中的任何内容，当 gcc 将 C 转换为 asm 时，事情通常不是这样工作的。另请参阅为什么打破 LZCNT 的“输出依赖关系”很重要？）
于 2009-03-23T15:16:34.103 回答
43
由于 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 位值。
于 2011-02-11T15:31:26.587 回答
42
假设您在 x86 和游戏中使用一些内联汇编程序，英特尔提供了一条BSR指令（“位扫描反向”）。在某些x86 上它很快（在其他上微编码）。从手册：
在源操作数中搜索最高有效设置位（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 节）它比循环代码快得多。
于 2009-03-23T00:00:51.713 回答
22
这有点像寻找一种整数对数。有一些小技巧，但我已经为此制作了自己的工具。目标当然是速度。
我的认识是 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才有这样的指令
于 2009-03-22T23:49:25.843 回答
19
这应该是闪电般的速度：
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];
}
于 2009-03-23T00:32:11.123 回答
12
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 位！
在输入 0x3FFFFFFFFFFFFFFF 上，决策树版本比在 1 上的要快很多，并且比移位器快 1120%（12.2 倍）。
我还将针对 GCC 内置函数对决策树进行基准测试，并尝试混合输入，而不是针对相同的数字重复。可能会出现一些粘滞分支预测，可能还有一些不切实际的缓存场景，这使得它在重复时人为地更快。
于 2011-12-11T07:43:13.517 回答
10
虽然我可能只在绝对需要最佳性能时才使用这种方法（例如，编写某种涉及位板的棋盘游戏 AI），但最有效的解决方案是使用内联 ASM。请参阅此博客文章的优化部分以获取带有解释的代码。
[...]，
bsrl汇编指令计算最高有效位的位置。因此，我们可以使用以下asm语句：asm ("bsrl %1, %0" : "=r" (position) : "r" (number));
于 2009-03-22T23:46:27.130 回答
9
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 指令快，后者在线性时间内运行。这是对数时间。
于 2009-03-23T03:21:45.957 回答
8
关于什么
int highest_bit(unsigned int a) {
int count;
std::frexp(a, &count);
return count - 1;
}
?
于 2013-12-01T01:17:13.527 回答
6
以下是本页当前给出的算法的一些（简单）基准......
该算法尚未针对 unsigned int 的所有输入进行测试；所以在盲目使用之前先检查一下；）
在我的机器上 clz (__builtin_clz) 和 asm 效果最好。asm 似乎比 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;
}
于 2011-07-08T14:20:26.307 回答
5
这里有一些过于复杂的答案。仅当输入已经是 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;
}
请注意，与大多数其他答案不同，此版本最后不需要 Debruin 查找。它计算就地位置。
但是，表可能更可取，如果您重复调用它足够多次，缓存未命中的风险就会因表的加速而黯然失色。
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;
}
这应该会产生此处给出的任何软件答案的最高吞吐量，但如果您只是偶尔调用它，则更喜欢像我的第一个片段这样的无表解决方案。
于 2016-08-16T06:33:17.217 回答
4
我需要一个例程来执行此操作，并且在搜索网络（并找到此页面）之前，我提出了基于二进制搜索的自己的解决方案。虽然我确信以前有人这样做过！它以恒定的时间运行，并且可以比发布的“明显”解决方案更快，尽管我没有提出任何伟大的主张，只是出于兴趣而发布它。
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;
}
于 2011-10-14T12:29:54.900 回答
4
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);
}
优点：无论提供多少，运行时间都是恒定的，因为循环的数量总是相同的。（使用“unsigned int”时有 4 个循环）
于 2014-11-24T09:44:41.070 回答
4
那是某种二进制搜索，它适用于各种（无符号！）整数类型
#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;
}
于 2015-05-21T12:32:17.160 回答
3
扩展 Josh 的基准......可以如下改进 clz
/***************** clz2 ********************/
#define NUM_OF_HIGHESTBITclz2(a) ((a) \
? (((1U) << (sizeof(unsigned)*8-1)) >> __builtin_clz(a)) \
: 0)
关于 asm：请注意有 bsr 和 bsrl（这是“长”版本）。正常的可能会快一点。
于 2011-07-09T08:14:18.067 回答
3
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)
An nof 也0UL需要防范，因为：
返回 -∞ 并引发 FE_DIVBYZERO
我写了一个示例，其中任意设置Index为ULONG_MAX此处的检查：https ://ideone.com/u26vsi
const auto n = 13UL;
unsigned long Index;
_BitScanReverse(&Index, n);
printf("MSB is: %u\n", Index); // Prints 3 (zero offset)
_BitScanReverse状态的文档Index是：
加载找到的第一个设置位 (1) 的位位置
在实践中，我发现 if nis 0ULthatIndex设置为0UL，就像对于 an nof一样1UL。n但是在 an of的情况下，文档中唯一保证的0UL是返回是：
如果没有找到设置位，则为 0
因此，与上面的优选实现类似，在这种情况下log2，应检查返回值是否设置Index为标记值。我在这里再次编写了一个使用ULONG_MAX此标志值的示例：http ://rextester.com/GCU61409
于 2015-01-12T19:05:36.007 回答
3
正如上面的答案所指出的，有多种方法可以确定最高有效位。但是，正如还指出的那样，这些方法可能是 32 位或 64 位寄存器所独有的。stanford.edu bithacks 页面提供了适用于 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;
}
于 2014-05-26T08:48:19.703 回答
3
我知道这个问题很老了，但是我自己实现了一个msb()函数，我发现这里和其他网站上提供的大多数解决方案不一定是最有效的 - 至少对于我个人对效率的定义（另见下面的更新）。原因如下：
大多数解决方案（尤其是那些采用某种二进制搜索方案或从右到左进行线性扫描的朴素方法的解决方案）似乎忽略了这样一个事实，即对于任意二进制数，没有多少以非常长的序列开头的零。事实上，对于任何位宽，所有整数中有一半以1开头，其中四分之一以01开头。看到我要说的了吗？我的论点是，从最高有效位位置开始到最低有效位（从左到右）的线性扫描并不像乍一看那样“线性”。
可以显示1，对于任何位宽，需要测试的平均位数最多为 2。这转化为O(1)相对于位数的摊销时间复杂度(!) .
当然，最坏的情况仍然是O(n)，比使用类似二进制搜索的方法得到的O(log(n))更糟糕，但是由于最坏的情况很少，因此对于大多数应用程序来说它们可以忽略不计（更新：不完全：可能很少，但它们可能发生的概率很高 - 请参阅下面的更新）。
这是我提出的“天真的”方法，至少在我的机器上胜过大多数其他方法（32 位整数的二进制搜索方案总是需要log 2 (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 位整数的 MSB 所需的时间），现实生活中的整数，对于将调用哪个这样的函数，通常遵循不同的模式：例如，在我的代码中，此函数用于确定对象大小是否为 2 的幂，或者查找大于或等于对象大小。我的猜测是，大多数使用 MSB 的应用程序涉及的数字远小于整数可以表示的最大数字（对象大小很少使用size_t中的所有位）。在这种情况下，我的解决方案实际上会比二分搜索方法执行得更差 - 所以后者可能应该是首选，即使我的解决方案将更快地循环遍历所有整数。
TL;DR：现实生活中的整数可能会偏向于这个简单算法的最坏情况，这将使其最终表现更差 - 尽管事实上它对于真正任意整数的摊销 O(1) 。
1论证如下（粗略）：设n为位数（位宽）。总共有2 n 个整数，可以用n位表示。有2 n - 1 个以1开头的整数（第一个1是固定的，剩余的n - 1位可以是任何值）。这些整数只需要一次循环即可确定 MSB。此外，有2 n - 2 个以01开头的整数，需要 2 次迭代，2 n - 3 个以001开头的整数，需要 3 次迭代，依此类推。
如果我们对所有可能的整数求和所有需要的迭代并将它们除以2 n （整数的总数），我们得到确定n位整数的 MSB 所需的平均迭代次数：
(1 * 2 n - 1 + 2 * 2 n - 2 + 3 * 2 n - 3 + ... + n) / 2 n
这一系列平均迭代实际上是收敛的，并且对于n向无穷大的限制为 2
因此，朴素的从左到右算法实际上对于任意位数具有O(1)的摊销常数时间复杂度。
于 2016-12-30T01:17:58.867 回答
2
想想按位运算符。
我第一次误解了这个问题。您应该生成一个 int 并设置最左边的位（其他位为零）。假设 cmp 设置为该值：
position = sizeof(int)*8
while(!(n & cmp)){
n <<=1;
position--;
}
于 2009-03-22T23:51:08.493 回答
2
哇，那是很多答案。我不抱歉回答一个老问题。
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;
}
这个答案与另一个答案非常相似......哦，好吧。
于 2017-05-27T20:35:03.083 回答
1
由于这是“另一种”方法，因此将其放入，似乎与已经给出的其他方法不同。
返回-1if x==0，否则返回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];
}
于 2012-10-14T20:36:04.150 回答
1
另一张海报提供了一个使用字节范围查找的查找表。如果您想获得更多性能（以 32K 内存而不是仅 256 个查找条目为代价），这里有一个使用15 位查找表的解决方案，在C# 7 for .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;
}
该表需要通过上面的代码进行一次性初始化。它是只读的，因此可以共享单个全局副本以进行并发访问。使用此表，您可以快速查找整数log 2，这就是我们在这里寻找的所有整数宽度（8、16、32 和 64 位）。
请注意，表条目0是未定义“最高设置位”概念的唯一整数，其值为-1。这种区别对于正确处理下面代码中的 0 值高位字是必要的。事不宜迟，以下是各种整数原语的代码：
ulong（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 优化。
我的正式回答到此结束；以下是与我运行的测试相关的替代测试候选人的一些随意注释和源代码链接，以验证上述代码的性能和正确性。
上面提供的版本，编码为 Tab16A 在多次运行中始终是赢家。这些不同的候选人，以积极的工作/临时形式，可以在这里、这里和这里找到。
1 名候选人。HighestOne_Tab16A 622,496 2名候选人。HighestOne_Tab16C 628,234 3 名候选人。HighestOne_Tab8A 649,146 4 名候选人。HighestOne_Tab8B 656,847 5 名候选人。HighestOne_Tab16B 657,147 6 名候选人。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（不安全）760,387 13 _test_B.HighestOne8（不安全）763,904 14 _test_A.HighestOne3（不安全）766,433 15 _test_A.HighestOne1（不安全）767,321 16 _test_A.HighestOne4（不安全）771,702 17 _test_B.HighestOne2（不安全）772,136 18 _test_B.HighestOne1（不安全）772,527 19 _test_B.HighestOne3（不安全）774,140 20 _test_A.HighestOne7（不安全）774,581 21 _test_B.HighestOne7（不安全）775,463 22 _test_A.HighestOne2（不安全）776,865 23 名候选人。HighestOne_NoTab 777,698 24 _test_B.HighestOne6（不安全）779,481 25 _test_A.HighestOne6（不安全）781,553 26 _test_B.HighestOne4（不安全）785,504 27 _test_B.HighestOne5（不安全）789,797 28 _test_A.HighestOne0（不安全）809,566 29 _test_B.HighestOne0（不安全）814,990 30 _highest_one_bit.HighestOne 824,345 30 _bitarray_ext.RtlFindMostSignificantBit 894,069 31 名候选人。HighestOne_Naive 898,865
值得注意的是 ntdll.dll!RtlFindMostSignificantBitvia 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 字节） （8 位）查找表相比，测试确实偏爱 32KB（和 64KB） short（16 位）直接查找表。byte我认为以下内容与 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];
}
在这个 SO question上有很多关于 deBruijn 方法的优越和伟大的讨论，我倾向于同意。我的猜测是，虽然 deBruijn 和直接查找表方法（我发现最快）都必须进行表查找，并且都具有非常小的分支，但只有 deBruijn 具有 64 位乘法运算。我只测试了IndexOfMSB这里的功能——不是 deBruijn——IndexOfLSB但我希望后者的机会更好，因为它的操作更少（见上文），我可能会继续将它用于 LSB。
于 2017-10-26T13:41:10.450 回答
1
请注意，您要做的是计算整数的整数 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);
}
于 2015-10-17T17:13:56.910 回答
1
有一个建议在 C 中添加位操作函数，特别是前导零有助于找到最高位集。见http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2827.htm#design-bit-leading.trailing.zeroes.ones
它们有望在可能的情况下作为内置实现，因此确保这是一种有效的方式。
这类似于最近添加到 C++（std::countl_zero等）中的内容。
于 2021-12-14T08:01:04.980 回答
1
我假设您的问题是针对整数（下面称为 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）。如果我忘记了什么，请告诉我。我还没有测试它，但它应该工作得很好。
于 2018-01-24T15:55:34.027 回答
1
这看起来很大，但与循环相比，它的工作速度非常快，感谢 bluegsmith
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);
}
}
}
}
}
于 2021-03-09T20:41:46.943 回答
0
编码：
// 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*Log2 X) 的整数部分
于 2015-06-29T10:21:10.360 回答
0
这是适用于GCC和Clang的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，则需要修改它。
于 2019-12-14T11:53:45.743 回答
0
我卑微的方法很简单：
MSB(x) = INT[Log(x) / Log(2)]
翻译：x的MSB是（Base x的Log除以Base 2的Log）的整数值。
这可以轻松快速地适应任何编程语言。在你的计算器上试一试，看看它是否有效。
于 2019-06-15T22:20:41.887 回答
-3
使用 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
}
于 2021-01-28T01:59:37.993 回答