首页   技术笔记   网址导航   Json在线解析   二维码   Ip地址查询   在线流程图  
新用户注册 | 会员登录
当前位置:  开发笔记 > 编程语言 > 正文

在C中以整数查找最高设置位(msb)的最快/最有效方法是什么？

作者：mylvfamily | 2023-08-29 08:04
如何解决《在C中以整数查找最高设置位(msb)的最快/最有效方法是什么？》经验，为你挑选了10个好方法。

如果我有一个整数n,并且我想知道最高位的位置(也就是说,如果最低有效位在右边,我想知道最左边位的位置是1),找出最快捷/最有效的方法是什么？

我知道POSIX支持ffs()strings.h中的一个方法来查找第一个设置位,但似乎没有相应的fls()方法.

是否有一些非常明显的方法可以解决这个问题？

如果你不能使用POSIX功能来实现可移植性呢？

编辑:如何在32位和64位架构上运行的解决方案(许多代码清单似乎只能在32位整数上运行).



1> ephemient..：

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的"输出依赖"很重要？)

MSVC将[_BitScanReverse](https://msdn.microsoft.com/en-us/library/fbxyd7zd.aspx)

2> timday..：

假设您使用的是x86和游戏中的一些内联汇编程序,英特尔会提供一条BSR指令("位扫描反转").这是快上一些 x86s(微代码对他人).从手册:

在源操作数中搜索最重要的设置位(1位).如果找到最高1位,则其位索引存储在目标操作数中.源操作数可以是寄存器或存储器位置; 目标操作数是一个寄存器.位索引是源操作数的位0的无符号偏移量.如果内容源操作数为0,则目标操作数的内容未定义.

(如果你在PowerPC上有类似的cntlz("计数前导零")指令.)

gcc的示例代码:

#include 

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

...好的,仔细观察就可以说"BSR只能在P3/Pentium-M/Core2 x86s上快速运行".Netburst和AMD的速度很慢.
实际上,该指令通常被微编码为循环并且相当慢.
哪一个 ？BSR还是CNTLZ？当我阅读上面提到的x86-timing.pdf时,BSR在Netburst Pentiums上的速度很慢.我对PowerPC一无所知.
@rlbond：呵呵，P4 Prescott上的BSR为2 oups，具有16个循环延迟（！），每4c吞吐量中有一个。但是在较早的Netburst上，它只有4个周期的延迟（仍为2微秒），每2c吞吐率只有一个。（来源：http：//agner.org/optimize/）。在大多数CPU上，它也依赖于gcc不能解释的输出（当输入为零时，实际行为是使目标保持不变）。这可能会导致类似http://stackoverflow.com/questions/25078285/replacing-a-32-bit-loop-count-variable-with-64-bit-introduces-crazy-performance之类的问题。IDK为什么gcc在修复该错误时会错过BSR。

3> Quinn Taylor..：

由于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位值.

@Chase:不,不是.这是无符号*的逻辑转移*.对于*signed*,它*可能是也可能不是逻辑移位(实际上它通常是算术的).
注意:必须是无符号的,对于有符号整数,对于负数,右移失败.
@Johan单步执行调试器可以帮助解释循环退出的原因.基本上,它是'因为条件中的表达式在最后一位向右偏移后计算为0(被视为假).
很好的想法使用最终结果:)
Xantix:C/C++的转变是一个逻辑转变,所以它工作正常.对于Java,JavaScript或D,您需要使用逻辑移位运算符`>>>`.可能还有比较器`!= 0`,以及一些未指定数量的括号.
"这比返回(unsigned int)log2(val)快2倍" - 最微弱的赞美.

4> Protagonist..：

这应该是闪电般的:

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

7位移位,5或指令,多次和潜在的高速缓存未命中.:)您是否对它进行了基准测试,或者查看生成的汇编程序？它*可能*最终会很慢,具体取决于编译器可以消除多少.
不是重点.它使用了比必要的更多数据缓存(多个缓存行,甚至更多),以及比必要更多的指令缓存.您可能会在第一次调用该函数时遇到缓存未命中,并且它会在不必要的情况下污染缓存,因此*在调用之后,其他代码可能会遇到超出必要的错误.LUT通常不值得麻烦,因为缓存未命中是昂贵的.但我只是说在我声称它"快速闪电"之前我想要进行基准测试.不是说它绝对是一个问题.
"可能的高速缓存未命中"可能是由于此代码需要访问其查找表.如果在调用此表时没有缓存该表,则在获取它时会有一个停顿.这可能使最坏情况的性能远远低于不使用LUT的解决方案.
该表有32个条目,每个值<255(127),因此将表定义为unsigned char类型,它将适合单个32字节L1高速缓存行.整个事情适合两个缓存行.
我是新来的.我没有得到负面投票的人.我提供了实际有效的源代码的唯一答案.

5> SPWorley..：

这有点像找一种整数日志.有点蠢蠢欲动,但我已经为此制作了自己的工具.当然,目标是速度.

我的意识是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获得这样的指令

在x86 CPU上,整数和浮点之间的转换可能会非常昂贵
Hacker's Delight解释了如何在5-3 Counting Leading 0中纠正32位浮点数中的错误.这是他们的代码,它使用匿名联合重叠asFloat和asInt:k = k&〜(k >> 1); asFloat =(float)k + 0.5f; n = 158 - (asInt >> 23); (是的,这取决于实现定义的行为)
是.由于类型别名优化,gcc会使用-O2这样的代码做一些讨厌的事情.

6> Kaz..：

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内置函数对决策树进行基准测试,并尝试混合输入而不是重复相同的数字.可能会有一些坚持的分支预测正在进行,也许还有一些不切实际的缓存场景,这使得它在重复时人为地加快了速度.

我并不是说这不好,但是你的测试程序只测试相同的数字,经过2-3次迭代后,将分支预测器设置到最终位置,之后它们将进行完美的分支预测.好处是,随机分布的一半,数字将接近完美预测,即bit63.

7> 小智..：

关于什么

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

？



8> Noldorin..：

虽然我可能只会使用这种方法,如果我绝对需要最好的性能(例如编写某种涉及位板的棋盘游戏AI),最有效的解决方案是使用内联ASM.有关解释的代码,请参阅此博客文章的"优化"部分.

[...],bsrl汇编指令计算最高位的位置.因此,我们可以使用这个asm声明:

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

@rlbound:我简直不敢相信,虽然我可能弄错了.在任何现代CPU上,人们会认为它会被翻译成单个指令....
@Noldorin有点晚了但是......根据定义,它只是一条指令,但是如果它是rlbond建议的微编码那么单指令可以在内部解码成一堆μops.对于AMD的微体系结构和英特尔凌动,情况往往如此,但在正常的英特尔微体系结构上,它只是单一操作.

9> 小智..：

以下是本页目前给出的算法的一些(简单)基准测试......

尚未对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;
}



10> rlbond..：
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

上面的代码没有回答这个问题.它返回一个无符号整数,其中x中位的最高有效位保持打开,所有其他位都关闭.问题是返回位上最重要的*位置*.
@Protagonist,他在评论中说,要么足够.
然后,您可以使用De Bruijn序列方法来查找已设置的位的索引.:-)
推荐阅读
devbox
mylvfamily
这个屌丝很懒，什么也没留下！
关注作者
Tags | 热门标签
RankList | 热门文章
DevBox开发工具箱 | 专业的在线开发工具网站    京公网安备 11010802040832号  |  京ICP备19059560号-6
Copyright © 1998 - 2020 DevBox.CN. All Rights Reserved devBox.cn 开发工具箱 版权所有