floor(x) 不等于 x 其中 x 是双精度

Question

我有一个简单的代码来检查 INTEGER n 是否是 2 的幂

bool isPowerOfTwo(int n)
{
    double x = log(n)/log(2);
    return floor(x) == x ;
}

大多数测试用例都很好，直到 n = 536870912 = 2^29。

在这种情况下，函数 return FALSE（这是不正确的）。我用 printf 打印 floor(x) 和 x，它们都给出 29.000000。但是，它仍然 return 是错误的。我 hexdump x 和 floor(x)

x:

01 00 00 00 00 00 3D 40

楼层（x）：

0000 00 00 00 00 3D 40

当x是一个整数(29)时，为什么floor(x)会改变x的某一位？如何解决这个问题？提前致谢。

仅供参考：

gcc 版本 9.3.0 (Ubuntu 9.3.0-17ubuntu1~20.04)
目标：x86_64-linux-gnu

编辑：有趣的是，如果将 log() 替换为 log10()，它工作正常。

Answer 1

您的方法不可靠，原因有多种：

如果 int 类型的值位多于浮点类型，则转换 int 可能会失去精度。将 long long 转换为 IEEE-754 double 类型时就是这种情况。
log(n) 和 log(2) 都是近似值：结果四舍五入到可表示为 double 的最接近值。将这些近似值相除可能不会产生 log₂(n) 的精确值，并且结果本身会四舍五入，因此即使是整数也可能不是证明 n 是 2 的精确幂。
如果 n 为负，log(n) 可能 return NAN 并且测试将评估为 false，但 log 可能触发信号并导致意外行为。 log(0) 可能 return -Infinity 或者也发送信号。
在这样的测试中，浮点计算不是预期的方法。利用整数的二进制表示是一个更好的解决方案。

一个更简单的方法是：

bool isPowerOfTwo(unsigned int n) {
    return (n & (n - 1)) == 0 && n != 0;
}

Answer 2

检查是否为 2 的幂以及是否为 returns log2(x)

的函数

#define MAX(x)     (CHAR_BIT * sizeof(x))
#define HALF(x)    (1UL << (MAX(x) / 2))

int ispower2andLog(unsigned x)
{
    int result = 0;
    
    if(x > HALF(x))
    {
        for(int pos = MAX(x) / 2; pos < MAX(x); pos++)
        {
            if((1UL << pos) == x)
            {
                result = pos;
                break;
            }
        }
    }
    else
    {
        for(int pos = 0; pos <= MAX(x / 2); pos++)
        {
            if((1UL << pos) == x)
            {
                result = pos;
                break;
            }
        }
    }
    return result;
}

int main(void)
{
    unsigned testcases[] = {0, 2,4, 5, 0x100, HALF(UINT_MAX) - 1, HALF(UINT_MAX) - 0, HALF(UINT_MAX) + 1, UINT_MAX & (~(UINT_MAX >> 1)), UINT_MAX};

    for(size_t i = 0; i < sizeof(testcases) / sizeof(testcases[0]); i++)
        printf("%12u (%08x) result = %d\n", testcases[i], testcases[i], ispower2andLog(testcases[i]));
}

Answer 3

Why would floor(x) change a certain bit of x when x is a round number (29)?

因为你用的double没有精确存储计算结果，所以四舍五入，又因为计算结果远离整数floor四舍五入到整数数字。在您的平台上 double 是 Double precision IEEE 745.

calculation	real result	rounded to double
log(536870912)	20.10126823623841397309	20.10126823623841474387
log(2)	.69314718055994530941	.69314718055994528623
20.10126823623841474387/.69314718055994528623	29.00000000000000208209	29.00000000000000355271
(double)log(536870912)/(double)log(2)	29.00000000000000000028	29.00000000000000355271

ln(536870912)/ln(2)的计算结果为29.00000000000000355271（即0x1.d000000000001p+4）。然后 Floor 截断 1 并给出准确的 29.

请注意 (double)log(536870912)/(double)log(2) 的结果如何更接近 29.00000000000000355271 而不是 29。您可以尝试 https://www.binaryconvert.com/convert_double.html# and https://www.h-schmidt.net/FloatConverter/IEEE754.html 来更好地学习浮点数。

How to fix this problem ?

通常的解决方案：通过使用更大的数据类型来提高精度（即使用 long double) 或使用任意精度的算术库。在这种情况下，根本不要使用浮点数，坚持使用整数。

Answer 4

下列 returns 为真当且仅当 n 是二的幂：

_Bool isPowerOfTwo(int n)
{
    return 0 < n && n == (n & - (unsigned) n);
}

- (unsigned) n 计算 n 的补码（因为无符号算术以 2 的幂为模进行换行）。在正数的二进制补码中，最低 1 位以上的所有位都发生变化。例如，0100 0110 更改为 1011 1010。因此，当它与原始数字进行 AND 运算时，唯一打开的位是最低的 1 位。如果这等于原始数字，则原始数字只有一位设置为 1，因此它是 2 的幂。如果它不等于原始数，则原始数不止一位设置为 1，因此它不是 2 的幂。（原始数字没有位设置为1的情况由测试0 < n处理。）

floor(x) 不等于 x 其中 x 是双精度

floor(x) does not equal x where x is a double

c

double