How to convert very large binary to decimal in C

Question

I'm using netBean to code C, and my assignment is convert a very large binary number to decimal ( the binary number maybe upto 100 digits), I'm very confuse because my program works when the binary number is about 50-60 digits but it will automatically crash on run-time when input is larger. I'm using long long int to store the decimal result but it seem doesn't work! Here is my code :

 long long int decimal = 0;
    int position = 0;
    for(int i = strlen(binaryInput)-1; i>=0; --i){
        if(binaryInput[i]=='1'){
            decimal += (long long int)(pow(2,position));
        }
        ++position;
    }
    printf("\nDecimal number is: %lli ", decimal);

'binaryInput' is my string to store binaryNumber from keyboard.

The `long long int` type is at minimum 64 bits. And signed. So how would you ever be able to fit up to 100 bits of data in it if it's only 64 bits (which is standard on modern PC systems)? — Some programmer dude, Oct 04 '17 at 08:44
Why not use the shift operator? Will be a lot faster than using `pow` repeatedly — Ed Heal, Oct 04 '17 at 08:44
`pow()` is a bad idea here, it operates on floating-point numbers. Use simple bit-shifts instead. And then, there's no integer type that can hold 100 bits (*binary digits!*) in your typical C implementation. You could try using non-standard `int128_t` types. You probably should use an array of unsigned types instead. Converting this to a decimal notation, have a look e.g. at [double dabble algorithm](https://en.wikipedia.org/wiki/Double_dabble#C_implementation). — , Oct 04 '17 at 08:44
Could you display the number as hexadecimal? If so you could translate any number of binary digits. Just take 4 bits at a time and convert them into hex. — Code Gorilla, Oct 04 '17 at 08:46
First of all, you need to choose an internal representation able to keep the desired result. That means some very _big_ int type, of size 100 bits at least (which `long long` doesn't fullfill). Or maybe an ASCII representation as an array of `char`-s...? — CiaPan, Oct 04 '17 at 08:48
I don't see why this would crash. Please provide a [MCVE]. When it "crashes", what output is displayed __exactly__? — Jabberwocky, Oct 04 '17 at 08:57
here's a sloppy program for reference: https://ideone.com/fReZaj — , Oct 04 '17 at 09:10

score 2 · Answer 1 · answered Oct 04 '17 at 18:57

Here is a hint:

The easiest solution is to actually take the long binary number, and split it in half (or quarters, or whatever.)

Keep track of which of these is the upper range of the binary number, and which of these is the lower end of the binary number.

Calculate what the true value of the lower range, and upper range is. After that add them together.

gsamaras · Answer 2 · 2017-10-04T16:27:28.763

1

long long int has a range of -9,223,372,036,854,775,807 to 9,223,372,036,854,775,807, as mentioned here. There is no way that 100 bits can fit in there. However, this type is signed, you could try with an unsigned one, but I do not see any assumption on your numbers to be non-negative.

You could try with int128_t which fits 128-bit signed, but this is not Standard (Why isn't there int128_t?).

Consider using an array of size 100, where each cell will store a digit. With this approach it is suggested that you use Double dabble algorithm, which is used to convert binary numbers into binary-coded decimal (BCD) notation.

If you need a library, then The GNU Multiple Precision Arithmetic Library could do the trick.

PS: Use bit-shifts instead of pow(), since it will operate on floating-point values, and will decrease the performance of your code.

edited Oct 04 '17 at 16:27

answered Oct 04 '17 at 08:50

gsamaras

71,951
46
188
305

the big problem with using an array is printing. How do you print something in decimal which spans over multiple array elements without a special algorithmic support? There should be some *bignum* library in 'c' which could provide it. – Serge Oct 04 '17 at 12:23
@Serge see my comments on the question -- use some variation of the double-dabble algorithm. – Oct 04 '17 at 15:38
@Serge I updated my answer, with Felix's insight and a library I had used in the past. – gsamaras Oct 04 '17 at 16:27

score 0 · Answer 3 · answered Nov 14 '19 at 20:42

Not sure if this is the most optimized technique. This can calculate up to 1000 digit. You can increase the array allocation to calculate longer binary numbers I used strings for input and high school mathematics technique for addition and calculate the power of 2

#include <bits/stdc++.h>
typedef long long int lli;
using namespace std;

int main() {

    char bin_number[1010];
    //variable for big integer operation 
    int int_number[1010], t_int_number[500];
    /*
     * int_number : converted decimal number will be stored here
     * t_int_number : will be used to calculate the power of 2
     */


    int bin_length, t_int_length, int_length, index;
    /*
     * bin_length   : length(bin_number)
     * t_int_length : length(t_int_length)
     * int_length   : length(int_length)
     */

    bool carry;

    while(scanf("%s", bin_number) != EOF) {                     //input binary number
        for (int i = 0; i < 500; i++) {                         //intialize decimal number to 0 and t_int_number to 0
            int_number[i] = 0;
            t_int_number[i] = 0;
        }

        //set t_int_number to 1 
        t_int_number[0] = 1;
        t_int_length = 1;
        //set the int_number to 0
        int_length = 1;
        index = 0;
        //calculate input length
        bin_length = strlen(bin_number);

        for (int i = bin_length - 1; i >= 0; i--) {                  //checks each digit of binary number
            //if the digit in binary representation is 1
            if (bin_number[i] == '1') {   
                //sum (int_number, t_int_number)
                for (int index = 0; index < t_int_length; index++) {
                    int_number[index] +=
                        t_int_number[index];                //sum t_int_number digits
                    if (int_number[index] > 9) {                //if carry
                        int_number[index + 1] ++;
                        int_number[index] -= 10;
                    }
                }
                int_length = index;
                if (int_number[index] != 0) {               //i f length increase for addition 
                    int_length ++;
                }
            }

            //Being ready for next iteration
            //multiplying everytime with 2 and save it to t_int_number
            carry = false;
            for (index = 0; index < t_int_length; index++) {
                t_int_number[index] += t_int_number[index];     //double the number
            }
            for (index = 0; index < t_int_length; index++) {
                if (t_int_number[index] > 9) {
                    t_int_number[index] -= 10;
                    t_int_number[index + 1]++;
                }
            }
            if (t_int_number[index] != 0) {
                t_int_length++;
            }
        }

        //printing the decimal number
        for (int i = int_length - 1; i >=0; i--) {
            printf("%d", int_number[i]);
        }
        printf("\n");
    }

    return 0;
}

How to convert very large binary to decimal in C

3 Answers3