Thread: Converting a char string into an integer and then into binary

Can you use a library for arbitrary-precision (such as The GNU MP Bignum Library) or do you have to implement this functionality from scratch as an assignment?

Firstly, you need to decide whether you really need to represent a large integral value as an intermediate step, given that you want to work with values that exceed the capacity of long long types. If so, you need to select some representation (say an array of integers) and work out how to unambiguously implement basic operations (addition, subtraction, multiplication, division, modulo, etc) on that representation.

From there, conversion of "integer values" back to binary is trivial: the binary digits (in reverse order) would be extracted by repeatedly computing the value modulo 2, subtracting that value, and then dividing by 2.

It would be easier (at least, for you coding it up) to avoid going by some intermediate representation as an "integer". Given an input string (say "1234567") it is fairly easy to go directly to binary: no need for any intermediate representation as an "integer". If the rightmost digit (7 in this case) is odd, the last binary digit is 1. If you keep subtracting 1 (if value is odd) or zero (if value is even) and dividing by 2 (which can be done by hand using a long division technique, and that type of logic can be coded up) you can extract the binary digits one at a time, in reverse order. Reverse the order, and you will find that "1234567" is represented in binary as "100101101011010000111"

Incidentally, the ASCII value is the actual value of a character (assuming your machine is using an ASCII character set). It is you who interprets a '0' as the digit zero, not the machine.

Grumpy makes a very important point. If the assignment is to take input like
72636418745281276354727103685721876829840592882608 7364852895
and print it out in binary, then you don't need the intermediate step of representing it as an "integer" at all. The char array is a good enough representation to get the bits from. You just need to be able to do a little arithmetic on it, in particular, you need to be able to divide it by 2.

EDIT: Why does this forum add a space after 50 consecutive characters?

Originally Posted by grumpy

If you keep subtracting 1 (if value is odd) or zero (if value is even) and dividing by 2

Actually, you won't have to subtract 1 since (integer) division by two will toss it out anyway.

Originally Posted by oogabooga

Actually, you won't have to subtract 1 since (integer) division by two will toss it out anyway.

Sure.

It depends on how division is implemented, actually - rounding up or rounding down are mathematical conventions, not absolute laws of how things should be done. And since one approach for the OP might be to implement division in different ways, I considered it better to spell out what happens .... even if some steps might be done implicitly rather than explicitly.

You have to be a little more clever than that.
Example

Code:

index: 0 1 2
char : 1 7 3

First, write a 1 or 0 depending on whether the last digit is odd or even, respectively.
So we write a 1.
Then divide the whole string by 2.
Start at the right-hand side.

3 / 2 = 1
Since this is the rightmost digit, we toss out the 0.5

Next digit:
7 / 2 = 3
Since this is NOT the rightmost digit, we can't just throw away the 0.5. Instead, you add 5 to the digit to the right.

1 / 2 = 0 and add 5 to the digit to the right.

This gives 0 8 6

Then start again at the beginning. This time you'll get a 0 bit since the number is even. Then divide by 2 again....

Keep going until the number is all zeros.

Originally Posted by Avanish Giri

What is the intuition behind that?

It is just long division as taught in many elementary/primary schools, combined with what you already know of using division to compute the bits of an integer. Refer to grumpy's post #6.

Also remember that the bits are going to come out in reverse order, so you'll have to store them up and print them backwards.