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

Question

I have a simple code to check if an INTEGER n is a power of 2

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

Most of the test cases are fine until n = 536870912 = 2^29.

In this case, the function return FALSE (which is not correct). I used printf to print floor(x) and x, both of them give 29.000000. But still, it returns FALSE. I hexdump x and floor(x)

x:

01 00 00 00 00 00 3D 40

floor(x):

00 00 00 00 00 00 3D 40

Why would floor(x) change a certain bit of x when x is a round number (29)? How to fix this problem ? Thanks in advance.

FYI:

• gcc version 9.3.0 (Ubuntu 9.3.0-17ubuntu1~20.04)
• Target: x86_64-linux-gnu

EDIT: interestingly, if log() is replaced with log10(), it works fine.

Answer 1

Function which checks if is the power of 2 and if it is 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 2

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

Because double you are using has no precision to store the result of calculations exact, so it rounds, and because the result of calculation is away from a whole number floor rounds to the whole number. On your platform double is 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

The result of calculation of ln(536870912)/ln(2) is 29.00000000000000355271 (i.e. 0x1.d000000000001p+4). Floor then truncates the 1 and gives exact 29.

Note how the result of (double)log(536870912)/(double)log(2) is closer to 29.00000000000000355271 then to 29. You can play around with https://www.binaryconvert.com/convert_double.html# and https://www.h-schmidt.net/FloatConverter/IEEE754.html to learn floats better.

How to fix this problem ?

The usuall solutions: increase precision by using greater datatype (i.e. use long double) or use an arbitrary-precision arithmetic library. In this case, do not use floating point numbers at all, stick to integers.

Answer 3

The following returns true iff n is a power of two:

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

- (unsigned) n computes the two’s complement of n (because unsigned arithmetic wraps modulo a power of two). In the two’s complement of a positive number, all bits above the lowest 1 bit change. For example, 0100 0110 changes to 1011 1010. So, when this is ANDed with the original number, the only bit on is the lowest 1 bit. If this equals the original number, the original number had only one bit set to 1, so it is a power of two. If it does not equal the original number, the original number had more than one bit set to 1, so it is not a power of two. (The case where the original number has no bits set to 1 is handled by the test 0 < n.)

Answer 4

Your method is not reliable for multiple reasons:

• converting an int might lose precision if the int type has more value bits than the floating point type. This would be the case when converting a long long to an IEEE-754 double type.
• both log(n) and log(2) are approximations: the result is rounded to the closest value representable as a double. Dividing these approximations might not produce the exact value of log₂(n), and the result is itself rounded so even a whole number might not be proof that n be an exact power of 2.
• if n is negative, log(n) might return a NAN and the test will evaluate to false, but log might trigger a signal and cause unexpected behavior. log(0) might return -Infinity or send a signal too.
• in a test like this, a floating point calculation is not the expected approach. Taking advantage of the binary representation of integers is a better solution.

A much simpler method is this:

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