different answers using pow() in c++ when used in different places, although same is expected

Question

I have shown two pieces of code. I don't quite understand how using pow() differently brings about a difference in these codes. Thanks a lot in advance.

In this problem you are to calculate the sum of all integers from 1 to n,but you should take all powers of two with minus in the sum.For example, for n = 4 the sum is equal to  - 1 - 2 + 3 - 4 =  - 4, because 1, 2 and 4 are 2⁰, 2¹ and 2² respectively. Calculate the answer for t values of n.

#include<bits/stdc++.h>    
typedef long long ll;
typedef double dl;
using namespace std;
int main() {
   ll n,t;

   ll i,cnt=0;
   cin>>t;
   while(t--)// for 't' number of test cases 
  {
       cin>>n;

           for(i=1,cnt=0;i<=n;i*=2,cnt++); //counting number of terms in the GP:1,2,4,....
           cout<<setprecision(20)<<((n*(n+1))/2)-(2*(pow(2,cnt)-1))<<endl;
  }
  return 0;

}
//output for above code:499999998352516352
// and the slightly modified code..


#include<bits/stdc++.h>
typedef long long ll;
typedef double dl;
using namespace std;
int main() {
    ll n,t;

    ll i,cnt=0;
    cin>>t;
    while(t--)// for 't' number of test cases
    {
    cin>>n;

    for(i=1,cnt=0;i<=n;i*=2,cnt++); 
    ll k=(pow(2,cnt)); //instead of directly printing the answer, 'k' is computed and then used to find the answer.
    cout<<setprecision(20)<<((n*(n+1))/2)-(2*(k-1))<<endl;
    }
    return 0;

}
//output for above code:499999998352516354
// the second one is the correct answer, the first one is wrong. how does pow() change the values here? 

Answer 1

Apparently the value of that is giving you trouble is n=1000000000, or 10⁹. The largest integral power of 2 less than or equal to this value is 2²⁹. The sum you are trying to calculate is thus (10^9*(10^9+1))/2-2*(2^30-1), or 500000000500000000-2147483646, or 499999998352516354.

Your second approach works because powers of two are exact and because you are using integer arithmetic in your subtraction. Your first approach fails because the expression is calculated as a double. The first term, n*(n+1)/2, or 500000000500000000, is "exact", which means there is no error in the floating point representation. The second term, 2147483646, is also exact. The problem in this case occurs with the subtraction. The difference between the two is inexact, which means you've lost precision.

There was no reason for you to use pow. You have already computed pow(2,cnt). In fact, you don't need cnt at all. Simply use

ll k;
for(k=1; k<=n; k*=2);