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

Question

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

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

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

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

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

Answer 1

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

Answer 2

假设您使用的是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节)它比循环代码快得多.

Answer 3

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

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

Answer 5

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

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

Answer 6

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

Answer 7

关于什么

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

？

Answer 8

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

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

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

Answer 9

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

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

Answer 10

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

Answer 11

这里有一些过于复杂的答案。仅当输入已经是 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;
}

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