首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >在C中查找整数中最高设置位(msb)的最快/最有效的方法是什么?

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

Stack Overflow用户
提问于 2009-03-23 07:37:23
回答 20查看 154.4K关注 0票数 137

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

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

有没有什么明显的方法是我没有注意到的?

如果不能使用POSIX函数实现可移植性,该怎么办呢?

编辑:一个同时适用于32位和64位体系结构的解决方案如何(许多代码清单似乎只适用于32位整数)。

EN

回答 20

Stack Overflow用户

发布于 2009-03-23 00:32:11

这应该是闪电般的速度:

代码语言:javascript
复制
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];
}
票数 19
EN

Stack Overflow用户

发布于 2011-12-11 15:43:14

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)。

代码语言:javascript
复制
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;
}

快速和肮脏的测试程序:

代码语言:javascript
复制
#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,差异会变得更大。决策树的速度几乎快了四倍。

我还对简单的位移位代码进行了基准测试:

代码语言:javascript
复制
int highest_bit_shift(long long n)
{
  int i = 0;
  for (; n; n >>= 1, i++)
    ; /* empty */
  return i;
}

正如人们所预期的那样,这只适用于较小的数字。在确定n == 1的最高位为1时,它的基准测试速度快了80%以上。然而,63位空间中随机选择的数字中有一半设置了63位!

在输入0x3FFFFFFFFFFFFFFFFFFF上,决策树版本比在1上快很多,并且比位移位器快1120% (12.2倍)。

我还将针对GCC内置的决策树进行基准测试,并尝试混合输入,而不是针对相同的数字重复输入。可能有一些粘滞的分支预测正在进行,也可能有一些不切实际的缓存场景,这使得它在重复时人为地加快了速度。

票数 12
EN

Stack Overflow用户

发布于 2009-03-23 03:21:46

代码语言:javascript
复制
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

票数 9
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/671815

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档