c - 查找数组中最大幅度元素的 MSB 集

Question

给定一个 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 个算术指令。所以我希望也许有一种高效的算法可以准确地找到我需要的东西。

Answer 1

看到你在 ARM 平台上工作，你可以在 2 条指令中使用以下 abs 的实现:

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(但无论如何您都应该尽可能多地展开)。

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