给定2^n，使用对数找到n

Question

给出一个2^n的整数，其中n是指数，我想通过对数找到n的索引值。用于查找索引的公式为：log(number) / log(2)。以下是代码片段：

  unsigned long int a;
  double apower;
  apower = log((double)a) / log((double)2);

我发现在某些很大的a值时，'apower'的值是错误的。我不知道具体的数值，因为我的代码提交后失败了。这是为什么？是否存在强制转换问题？

以下是完整的代码片段：

  int count = 0;
  unsigned long int a,b;
  double apower,bpower;
  apower = log((double)a) / log((double)2);
  bpower = log((double)b) / log((double)2);
  count = abs(apower - bpower);
  printf("%d\n",count);

a和b的值将始终是2的幂次方。因此，apower和bpower必须在小数位上有00。这就是为什么count的值将是int（%d）。我只想了解对数的行为。

- user2737359

---

为什么你会在 a 上使用 unsigned long int，如果你最终还是将其转换为 double？这毫无意义... - Nidhoegger

我写了一个小的测试程序，利用了你的代码。当n太大超过unsigned long int的范围时，它就无法工作了，此时结果为-inf，这是正确的行为。所以请提供更多关于你的作业...抱歉...你的问题的信息。 - Nidhoegger

数数末尾有多少个零？编译器内置函数可以做到。在gcc中，使用__builtin_ctz()可以对int类型计算，对于long类型则使用__builtin_ctzl()，long long类型则使用__builtin_ctzll()。其他编译器可能也有相应的函数。 - EOF

@Nidhoegger：如果这些整数是2的幂次方，那么可以将它们转换为双精度浮点数（甚至单精度浮点数）而不会有损失。 - Stefan Haustein

输入值为10^17，因此我使用了无符号长整型。 - user2737359

Answer 1

我只回答你问题的一半，因为用日志来解决这个问题是不必要的。一个简单的方法是使用以下内容：

unsigned long long a = 0x8000000000000000ULL;
int n = 0;
while (a >>= 1) n++;
printf("%d\n", n);

输出：

63

将其转换为对数并除以可能会导致精度损失，在这种情况下，应使用 round。您使用了“提交”一词，所以这是一个在线挑战失败了吗？您到底打印了什么？（在这种情况下）63.000000？这将从默认格式%f得到。

- Weather Vane

---

计算整数对数的更快方法。 (https://graphics.stanford.edu/~seander/bithacks.html#IntegerLog) - serge-sans-paille

我想避免循环，以便结果在O(1)中出现。 - user2737359

Answer 2

为什么不利用double类型指数字段中存储的log2呢？ :)

unsigned long long a = 0x8000000000000000ULL;
union {
  double d;
  unsigned long long l;
} u;
u.d = a;
int apower = (u.l >> 52) - 1023;
printf("%d\n", apower);

输出：

63

这里假设无符号长整型和双精度浮点数都是64位，并且输入值大于0。

- Stefan Haustein

---

@EOF: 不是太认真，但在Stack Overflow上的无数log2问题中都没有看到过这个，我一直想尝试一下 :) - Stefan Haustein

细节问题已在版权声明中解决 O:) - Stefan Haustein

frexp函数可以使这一过程以可移植的方式实现。 - Ben Voigt

如果您有非规范化的浮点数，即接近零的数字无法以规范化形式存储，那么这是否会产生问题？ - Matthias Wimmer

@MatthiasWimmer 这个问题说：“给定一个2的n次方的整数”。 - Stefan Haustein

Answer 3

当使用双精度浮点数进行数学计算时，对数或商可能不是精确的数学结果，而是比其大1（或2）的可表示双精度浮点数。

仅计算log（）会返回一个精确的数学结果，用于log（0），所有其他数学结果都是无理数。所有双精度浮点数都是有理数。

这可能导致像29.999999...这样的答案，将其保存为int类型则为29。

建议改用整数运算。

---

int mylog2(unsigned long x) {
  int y = 0;
  #if (ULONG_MAX>>16 > 1lu<<16)
    if (x >= 1lu<<32) { x >>= 32; y += 32;
  #endif
  if (x >= 1lu<<16) { x >>= 16; y += 16; }
  if (x >= 1lu<<8) { x >>= 8; y += 8; }
  if (x >= 1lu<<4) { x >>= 4; y += 4; }
  if (x >= 1lu<<2) { x >>= 2; y += 2; }
  if (x >= 1lu<<1) { x >>= 1; y += 1; }
  return y;
}

- chux - Reinstate Monica