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:
EDIT: interestingly, if log() is replaced with log10(), it works fine.
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.