Why is my answer off for certain values of binary representation provided?

user_9793339 0
Viewed 59

The question basically asks us to convert the input binary string (only 1 and 0 provided). Input format is as follows (each separate point is a new line):

  • Number of test cases
  • 2N lines with: Length of binary string, Binary string on each alternative line Output is to return the decimal conversion of the string.

My code:

#include <iostream>
#include <cmath>
using namespace std;

int main(){
    int t;
    cin >> t;
    while(t--){
        int len;
        cin >> len;
        long long num = 0;
        while(len--){
            char digit;
            cin >> digit;
            num += (digit-'0')*pow(2,len);
        }
        cout << num << endl;
    }
    return 0;
}

Ik there are other methods to go about this problem, but i want to know whats the problem in mine. Inputting certain values like '10001011111110111010111011010011011011110001011000011101' gives an answer '39401750052935200' when the correct value is '39401750052935197'.

Other examples of wrong output:

  • 269908306298371776 (correct = 269908306298371795)
  • 1152921504606846976 (correct = 1152921504606846975)

My code runs correct for all smaller values of binary input (of length maybe less than 50). Why does it fail for such larger values by such a small margin?

binary c++
1 Answers

runs correct for all smaller values of binary input (of length maybe less than 50).

num += (digit-'0')*pow(2,len); is like

num = num + (digit-'0')*pow(2,len);

and the addition is done using double math with its 53-ish bit precision infected by pow().

Instead only use integer math:

unsigned long long num = 0;
...
  num = num*2 + (digit-'0');
user_24103590
Related