除以2的幂会导致浮点数

Question

我发现自己需要计算16位无符号整数除以2的幂，结果应该是32位浮点数（标准IEEE格式）。这是在嵌入式系统上，且该例程会被重复使用，因此我正在寻找比(float)x/(float)(1<<n)更好的解决方案。此外，C编译器非常有限（没有数学库、位字段、reinterpret_cast等）。

- CoderSS

---

我怀疑你如果没有汇编语言，就很难变得更好，除非有一些编译器内嵌函数。另外，要进行性能分析、性能分析、性能分析。 - Antimony

我猜你的意思是“比(float)x/float(y)更好，其中y是2的某个幂次方”？还有，你所说的“更好”是什么意思？ - Xyzk

我正在寻找更好的性能。 - CoderSS

Answer 1

如果您不介意进行一些位操作，那么显而易见的方法是将整数转换为浮点数，然后从指数位中减去n以实现2^n的除法：

y = (float)x;                          // convert to float
uint32_t yi = *(uint32_t *)&y);        // get float value as bits
uint32_t exponent = yi & 0x7f800000;   // extract exponent bits 30..23
exponent -= (n << 23);                 // subtract n from exponent
yi = yi & ~0x7f800000 | exponent;      // insert modified exponent back into bits 30..23
y = *(float *)&yi;                     // copy bits back to float

请注意，当x = 0时此操作会失败，因此在进行转换之前应检查x > 0。

总成本包括一个int-float转换和一些整数位运算/算术运算。如果使用联合体，可以避免具有单独的int/float表示，并直接在float上工作。

- Paul R

---

谢谢。我也在考虑类似的东西，但不知道如何进行强制转换。我想你是指 uint32_t exponent = yi & 0x7f800000; 再次感谢！！！ - CoderSS

我现在没有我的电脑，所以还不能进行核对。但是，如果我们执行y = (float)x时，是否应该担心某些编译器会将x规范化（例如，x = 15，则1.5E + 1存储在y中，而不是15E + 0）。然后，修改指数部分将无法正常工作。 - CoderSS

不 - 在IEE754格式中，指数总是2的幂 - 数字是否被规范化并不重要。 - Paul R

如原文所述，没有必要提取指数来进行减法运算；可以直接在原地完成：yi -= n << 23;。然而，当 x 为零时，此代码会失败。 - Eric Postpischil

如果编译器支持复合字面量，则可以通过 uint32_t yi = (union { float f; uint32_t u; }) { y } .u 重新解释浮点数的位，并通过 y = (union { uint32_t u; float f; }) { yi } .f 将其重新解释回来。如果编译器不支持复合字面量，则可以定义一个联合对象以达到相同的效果。这避免了违反 C 标准未定义的指针别名规则。 - Eric Postpischil

Answer 2

使用ldexpf(x，-n)。标准C语言已经定义了这个函数，可以准确地返回你想要的值，即x•2^-n，所以任何一个好的编译器都会针对这个函数提供优秀的代码。（这需要数学库的一部分或者一个将其优化为内联代码的编译器。）

如果在编译时知道n的值，您还可以考虑x * (1.f/(1<<n))。一个好的编译器将在编译时计算出(1.f/(1<<n))，因此可执行代码会变成两个操作：将x转换为float并乘以一个常量。如果编译器没有像它应该做的那样对ldexpf(x，-n)进行优化，那么这可能比ldexpf(x， -n)产生的代码更快。

- Eric Postpischil

---

除了用户指定的“此外，C编译器相当有限（没有数学库、位字段、reinterpret_cast等）。”之外，如果能提供其他答案那就太好了。而且这个函数在数学库里。 - CashCow

Answer 3

一个快速简单的解决方案是预先计算一个浮点数值表，该表包含 2^-n 的值，其中 n >= 0 （n 的上限大约为 31），然后将 x 乘以表中的第 n^th 个元素。

如果您的代码模拟浮点乘法，这可能不是最快的方法，因为 CPU 不支持直接操作浮点数。但是，您可以只使用整数运算来更快地完成此操作。

例如（假设使用 IEEE-754 32 位浮点数）：

#include <limits.h>
#include <string.h>
#include <stdio.h>

#define C_ASSERT(expr) extern char CAssertExtern[(expr)?1:-1]

C_ASSERT(CHAR_BIT == 8);
C_ASSERT(sizeof(float) == 4);
C_ASSERT(sizeof(int) == 4);

float div(int x, unsigned n)
{
  float res;
  unsigned e = 0;
  unsigned sign = x < 0;
  unsigned m = sign ? -x : x;  

  if (m)
  {
    while (m >= (1u << 24))
      m >>= 1, e++;

    while (m < (1u << 23))
      m <<= 1, e--;

    e += 0x7F + 23;

    e -= n; // divide by 1<<n

    m ^= 1u << 23; // reset the implicit 1

    m |= (e & 0xFF) << 23; // mix in the exponent

    m |= sign << 31; // mix in the sign
  }

  memcpy(&res, &m, sizeof m);

  return res;
}

void Print4Bytes(unsigned char buf[4])
{
  printf("%02X%02X%02X%02X ", buf[3], buf[2], buf[1], buf[0]);
}

int main(void)
{
  int x = 0x35AA53;
  int n;
  for (n = 0; n < 31; n++)
  {
    float v1 = (float)x/(1u << n);
    float v2 = div(x, n);
    Print4Bytes((void*)&v1);
    printf("%c= ", "!="[memcmp(&v1, &v2, sizeof v1) == 0]);
    Print4Bytes((void*)&v2);
    printf("%14.6f %14.6f\n", v1, v2);
  }
  return 0;
}

输出 (ideone)：

4A56A94C == 4A56A94C 3517011.000000 3517011.000000
49D6A94C == 49D6A94C 1758505.500000 1758505.500000
4956A94C == 4956A94C  879252.750000  879252.750000
48D6A94C == 48D6A94C  439626.375000  439626.375000
4856A94C == 4856A94C  219813.187500  219813.187500
47D6A94C == 47D6A94C  109906.593750  109906.593750
4756A94C == 4756A94C   54953.296875   54953.296875
46D6A94C == 46D6A94C   27476.648438   27476.648438
4656A94C == 4656A94C   13738.324219   13738.324219
45D6A94C == 45D6A94C    6869.162109    6869.162109
4556A94C == 4556A94C    3434.581055    3434.581055
44D6A94C == 44D6A94C    1717.290527    1717.290527
4456A94C == 4456A94C     858.645264     858.645264
43D6A94C == 43D6A94C     429.322632     429.322632
4356A94C == 4356A94C     214.661316     214.661316
42D6A94C == 42D6A94C     107.330658     107.330658
4256A94C == 4256A94C      53.665329      53.665329
41D6A94C == 41D6A94C      26.832664      26.832664
4156A94C == 4156A94C      13.416332      13.416332
40D6A94C == 40D6A94C       6.708166       6.708166
4056A94C == 4056A94C       3.354083       3.354083
3FD6A94C == 3FD6A94C       1.677042       1.677042
3F56A94C == 3F56A94C       0.838521       0.838521
3ED6A94C == 3ED6A94C       0.419260       0.419260
3E56A94C == 3E56A94C       0.209630       0.209630
3DD6A94C == 3DD6A94C       0.104815       0.104815
3D56A94C == 3D56A94C       0.052408       0.052408
3CD6A94C == 3CD6A94C       0.026204       0.026204
3C56A94C == 3C56A94C       0.013102       0.013102
3BD6A94C == 3BD6A94C       0.006551       0.006551
3B56A94C == 3B56A94C       0.003275       0.003275

- Alexey Frunze

---

我有一种感觉，在2的补码系统中，这可能会对最小值失败。 - S.S. Anne