4

如它是否在 2^3 - 2^4、2^4 - 2^5 等范围内。返回的数字将是 EXPONENT 本身（减去偏移量）。

如何尽可能快速有效地完成这项工作？这个函数会在一个极度依赖速度的程序中被调用很多次。这是我当前的代码，但是因为它使用了 for 循环，所以效率太低了。

static inline size_t getIndex(size_t numOfBytes)
{
    int i = 3;
    for (; i < 32; i++) 
    {
        if (numOfBytes < (1 << i)) 
            return i - OFFSET;
    }
    return (NUM_OF_BUCKETS - 1);
}

非常感谢！

4

7 回答 7

9

据我所知，您所追求的只是 log 2 ( n )。

如果您的目标体系结构具有可以执行此操作的指令，则可能值得作弊并使用一些内联汇编。有关硬件支持的大量讨论和信息，请参阅有关“查找第一组”的Wikipedia 条目。

于 2012-08-14T18:15:13.100 回答
5

一种方法是找到设置为 1 的最高位。我正在尝试考虑这是否有效，因为在最坏的情况下您仍然需要进行 n 次检查。

也许你可以做一个二进制搜索风格，检查它是否大于 2^16，如果是，检查它是否大于 2^24（假设这里是 32 位），如果不是，然后检查它是否大于 2^20等... 那将是 log(n) 检查，但我不确定位检查与完整 int 比较的效率。

可以得到一些性能数据。

于 2012-08-14T18:09:16.123 回答
1

在 Sean Eron Anderson 的优秀Bit Twiddling Hacks页面中描述了一种使用 de Bruijn 序列的特别有效的算法：

uint32_t v; // find the log base 2 of 32-bit v
int r;      // result goes here

static const int MultiplyDeBruijnBitPosition[32] = 
{
  0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
  8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
};

v |= v >> 1; // first round down to one less than a power of 2 
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;

r = MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27];

它可以在没有分支的情况下进行 13 次操作！

于 2012-08-14T18:22:51.063 回答
1

您可以使用浮点数表示：

double n_bytes = numOfBytes

取指数位应该会给你结果，因为浮点数表示为：

(-1)^S X (1. + M) X 2^E

其中： S - 符号 M - 尾数 E - 指数

要构造掩码和移位，您必须阅读您正在使用的浮点类型的确切位模式。

CPU 浮点支持为您完成了大部分工作。

更好的方法是使用内置函数：

double frexp (double x, int * exp );

浮点表示

于 2012-08-14T18:53:26.157 回答
1

您基本上是在尝试计算：floor(log2(x))

取对数以 2 为底，然后取地板。

在 C 中执行此操作的最可移植的方法是使用该函数，该函数找到以elogf()为基数的日志，然后调整： log2(x) == logf(x) / logf(2.0)

在此处查看答案：如何在 c/c++ 中编写日志库（2）

如果您只是将生成的浮点值转换为，则同时进行int计算。floor()

但是，如果它可供您使用并且您可以使用它，那么有一种非常快速的方法可以计算log2()浮点数：logbf()

从手册页：

   The inte-
   ger constant FLT_RADIX, defined in <float.h>, indicates the radix  used
   for  the  system's  floating-point  representation.  If FLT_RADIX is 2,
   logb(x) is equal to floor(log2(x)), except that it is probably faster.

http://linux.die.net/man/3/logb

如果您考虑浮点数的存储方式，您会意识到该值floor(log2(x))是数字的一部分，如果您只是提取该值，您就完成了。一点点移位和位掩码，并从指数（或技术上的“有效数字”）中减去偏差，你就有了。计算floor(log2(x))任何浮点值的最快方法x。

http://en.wikipedia.org/wiki/Single_precision

但实际上logbf()在将结果提供给您之前将结果转换为浮点数，并处理错误。如果您编写自己的函数来将指数提取为整数，它会稍微快一些，并且整数就是您想要的。如果您想编写自己的函数，则需要使用 Cunion来访问浮点数中的位；尝试使用指针会给你带来与“类型双关”相关的警告或错误，至少在 GCC 上是这样。如果您询问，我将详细说明如何执行此操作。我以前写过这段代码，作为一个inline函数。

如果您只有一小部分数字要测试，您可以将您的数字转换为整数，然后使用查找表。

于 2012-08-14T18:37:31.833 回答
0

这在任何具有硬件浮点单元的机器上通常都很快：

((union { float val; uint32_t repr; }){ x }.repr >> 23) - 0x7f

它所做的唯一假设是浮点是 IEEE 并且整数和浮点字节序匹配，这两者在基本上所有现实世界的系统（当然是所有现代系统）上都是正确的。

编辑：当我过去使用它时，我不需要它来处理大量数据。Eric 指出，对于不适合浮点数的整数，它会给出错误的结果。这是一个修订版（尽管可能较慢），它修复了该问题并支持高达 52 位的值（特别是所有 32 位正整数输入）：

((union { double val; uint64_t repr; }){ x }.repr >> 52) - 0x3ff

另请注意，我假设x是一个正数（不仅是非负数，也非零）。如果x是负数，你会得到一个虚假的结果，如果x是 0，你会得到一个很大的负数结果（近似负无穷大作为对数）。

于 2012-08-14T23:09:39.993 回答
0 
#include <Limits.h>  // For CHAR_BIT.
#include <math.h>    // For frexp.
#include <stdio.h>   // For printing results, as a demonstration.


// These routines assume 0 < x.


/*  This requires GCC (or any other compiler that supplies __builtin_clz).  It
    should perform well on any machine with a count-leading-zeroes instruction
    or something similar.
*/
static int log2A(unsigned int x)
{
    return sizeof x * CHAR_BIT - 1 - __builtin_clz(x);
}


/*  This requires that a double be able to exactly represent any unsigned int.
    (This is true for 32-bit integers and 64-bit IEEE 754 floating-point.)  It
    might perform well on some machines and poorly on others.
*/
static int log2B(unsigned int x)
{
    int exponent;
    frexp(x, &exponent);
    return exponent - 1;
}


int main(void)
{
    // Demonstrate the routines.
    for (unsigned int x = 1; x; x <<= 1)
        printf("0x%08x:  log2A -> %2d, log2B -> %2d.\n", x, log2A(x), log2B(x));

    return 0;
}
于 2012-08-15T00:28:20.537 回答