c - 在 C 中反转 2 的幂的最快方法是什么？

Question

在等式中:

用 C 语言找到具有给定的二值幂 (a) 的 x 的最快方法是什么？

编辑:

1. 数学精确解是:
2. 由于(a)是一个正整数和一个2的幂(没有有理数，不等于0)，这道题可以简化为"looking for position of set bit" .
3. 这篇文章的重点是精简版嵌入式 CPU 系统。例如:ARM CORTEX M4。

---

a 到 x 结果:

  a | x
 -------
  1 | 0
  2 | 1
  4 | 2
  8 | 3
 16 | 4
 32 | 5
 64 | 6
128 | 7
256 | 8
512 | 9
...

---

选项 1:脏循环

unsigned int get_power_of_two_exponent(unsigned int value)
{
    unsigned int x = 0;

    while( ( 1 << x ) != value)
    {
        x ++;
    }

return x;
}

---

选项 2:奇怪的把戏

#include <stdint.h>

#if defined(__GNUC__)
static int highest_bit_set(uint32_t value)
{
    if (sizeof (unsigned int) == sizeof value)
        return 31 - __builtin_clz(value);
    else
    if (sizeof (unsigned long) == sizeof value)
        return 31 - __builtin_clzl(value);
    else
        exit(127); /* Weird architecture! */
}
#endif

---

有没有更快的选择？

Answer 1

最快 在 C 中几乎总是以内存使用为代价的查找表。假设该值始终恰好是 2 的幂，您可以制作这样的查找表:

uint8_t get_exponent (uint8_t val)
{
  static const uint8_t byte[256] = 
  {
    [1]   = 0,
    [2]   = 1,
    [4]   = 2,
    [8]   = 3,
    [16]  = 4,
    [32]  = 5,
    [64]  = 6,
    [128] = 7,
  };

  return byte[val & 0xFF];
}

如果您传递的值不是 2 的幂，它将返回 0。

这可以进一步扩展，例如循环遍历 uint32_t 的 4 个字节并进行 4 次表查找。或者制作更大的查找表。

在 x86 上，我将上面的内容归结为这个微小的、无分支的机器代码:

get_exponent:
        movzx   edi, dil
        movzx   eax, BYTE PTR byte.2173[rdi]
        ret

(在这种情况下，切换到 uint_fast8_t 会给出相同的代码。)