CODEWITHSUNDEEP
c
user3891236
user3891236

Reputation: 607

C: Converting a very large integer into a binary

I am trying to convert decimal Nos. into binary. The code works pretty fine (Windows 7 , 32 bit MS-VS2010): 

int main()
{

    int k, n;  
    int binary[100];
    printf("Enter the value in  decimal \n ");
    scanf("%d", &k);
    n = (log(k * 1.0) / log(2 * 1.0)) + 1  ; //total no. of binary bits in this decimal 

    for (int i = n; i > 0; i--)
        {
        binary[i] = k % 2;
        k /= 2;
        }

 return 0; 

}

But the limitation is that it works for Int size values only i.e. 32 bit. I want to modify this code so that it works for 2048 bits (decimal numbers containing 617 digits actually). I am not allowed to use any library.

Can someone give me some pointers how to proceed to tackle this?

Can someone give an example code snippet say for 64 bits ? Then I can use this to extend to higher values.

Update

1-As per suggestions I am trying to use strings. But I am not able to understand how to convert an String into large Int (I cant use stoi() as thsi will convert to 32 bit int , right? ).

2- Secondly I have to find:

log(222121212213212313133123413131313131311313154515441315413451315641314563154134156313461316413415635154613415645156451434)

Is the library function log capable of finding this ? Then what is the solution?

Upvotes: 1

Views: 3476

Answers (3)

legends2k
legends2k

Reputation: 32904

Since you told that you just need some pointers and not the actual answer, here goes:

I am not able to understand how to convert an String into large Int

That's because you can't. If you want to convert a number that huge to a numerical type, in the first place you need such a type that can hold numbers that big. The language doesn't provide you anything more than long long which is usually 128-bits long (i.e. if you can use C99, or just long which is usually lesser than a long long). Since your tutor told you not to use any external library, it's a clear sign that s/he wants you to code the solution using what's available only in the language and perhaps additionally the standard library.

Is the library function log capable of finding this

No, you can't use stoi or log since all of these expect arguments of some arithmetic type, while none of those built-in types are that big to hold numbers this huge. So you've to work completely with strings (i.e. either static or dynamic char buffers).

I understand that you want to use log to deduce the number of digits the binary output would need; but there's another option, which is to not know the number of digits before hand and allocate them dynamically with some upper bound so that you needn't re-allocate them further.

Lets take an example.

  1. Allocate 3 char buffers in, out (length of input) and bin (length of input * 4).
  2. Copy input to in
  3. While in is not "0" or "1" do else goto 12
  4. For each element ch in in do else goto 10
  5. Convert ch to integer i
  6. If is_odd = 1 then i += 10
  7. quot = i / 2
  8. Append quot to out
  9. is_odd = quot % 2; goto 4
  10. If is_odd = 1 append '1' else '0' to bin
  11. Copy out to in, reset out and goto 3
  12. Append in to bin
  13. Print bin in reverse

When you integer divide a number by 2, the quotient would always be less than or equal to the number of digits of the dividend. So you could allocate in and out with the same size as the input and use it for all iterations. For the bin buffer, the knowledge that each decimal digit wouldn't take more than 4 bits (9 takes a nibble, 1001) would help. So if the input is 10 digits, then 10*4 = 40 bytes would be the upper limit needed for bin buffer and 10 bytes would be needed for the in and out buffers.

This is a vague write-up of an algorithm, I hope it conveys the idea. I feel writing code is more easier than writing algorithms properly.

Upvotes: 1

mvw
mvw

Reputation: 5105

Regarding the update:

Grinding it through WolframAlpha gives:

log(222121212213212313133123413131313131311313154515441315413451315641314563154134156313461316413415635154613415645156451434)

is roughly

274.8056791141317511022806994521207149274321589939103691837589..

Test:

Putting it into exp gives:

2.2212121221321231313312341313131313131131315451544131541.. × 10^119

This raises the question about the precision you need.

Note: I assumed you mean the natural logarithm (base e).

Upvotes: 0

msporek
msporek

Reputation: 1197

I'm afraid there are no standard types in C that will allow you to store such a big value with 20148 bits... You can try to read the string from console (not converting into int), and then parse the string into "010101...." on your own.

The approach would be like that:
You should go for "dividing" the string by 2 in each step (for each division by 2 you need to divide all digits of the string by 2, and handle special cases like 11 / 2 => 5), and for each step if the value cannot be divided by 2, then you then you can put "1" as another binary digit, otherwise you put "0". This way you gather the digits '0', '1', '0', '1', etc. one by one. Then finally you need to reverse the order of digits. A similar approach implemented in C# you can find here: Decimal to binary conversion in c #

Upvotes: 0

Related Questions