4

len给定一个类型元素的数组，signed short它是在数组中的最大绝对值元素中找到最高有效位集合的位置。例如，如果数组 L 包含{-134, 123, 0, -890}，f(L)则应返回floor(log2(abs(-890)))+1.

这是我当前的功能：

short MSBSetMaxMagnitude(const short *p, int len)
{
   unsigned int t = 0;

   while (len > 0)
   {
      t |= abs(*p);
      p++;
      len--;
   }
   if(t)
      return (short)(32 - __builtin_clz(t));
   else
      return 0;
}

但是，由于 abs() 函数需要分支，所以它有点慢。我尝试使用不带分支的 abs() 代替，但它甚至更慢，因为它包含至少 3 个算术指令。所以我希望也许有一种有效的算法可以准确地找到我需要的东西。

4

2 回答 2

1

看到你在ARM平台上工作，你可以使用absin 2指令的以下实现：

EORS r1, r1, r1, ASR #32 (x = x ^ (x >> 32); carry_flag = sign_bit)
ADC r1, r1, #0           (add the sign_bit to x)

如果您可以容忍计算中 +/-1 的误差，请删除第二条指令；然后，你可以用 C 来表达它：

int abs_almost_exact(int x)
{
    return x ^ (x >> 32);
}

但是，更大的问题是循环。您可能会从展开中受益匪浅（因为每次迭代都没有什么可做的）：

do { // assuming len is even!
    int value1 = *p++;
    int value2 = *p++;
    value1 = abs(value1); // or replace abs by the hand-made version
    value2 = abs(value2);
    t |= value1;
    t |= value2;
    len--;
}
while (len > 0);

注意：我替换while {}为是do {} while因为我使用的编译器（ARM 编译器）以这种方式生成更好的代码。

另请注意，short从内存（在我使用的处理器上）加载变量时，ARM 有 2 个时钟周期的延迟。因此，最小展开因子为 3（但无论如何您都应该尽可能多地展开）。

哦，您的处理器是否支持short从内存中读取（半字）变量？我听说过一些非常古老的处理器无法做到这一点。如果是这种情况，您应该更改代码以一次加载 2 个值（1 个字），并使用一些位摆弄将它们分开。

于 2012-11-22T18:12:50.003 回答
0

三个算术指令在任何现代处理器上都应该花费很少的时间。您正在执行两个算术运算和一个条件分支来管理循环和索引。缓慢可能是由于数据缓存未命中和循环的组合造成的，由于指针使用和指针运算，编译器可能难以展开。

如果不查看数组中的每个元素，就无法找到依赖于数组中每个元素的值，因此目标应该是确保整个过程在扫描数组所需的时间内运行。

您可以通过替换来测试这是否是问题：

t |= abs(*p);

与 t |= *p;

如果这不是更快，我建议在手动展开循环中尝试非分支 abs 版本。

于 2012-11-22T17:31:43.543 回答