3

I have a string that consists some decimal value, with number of digits can be more than any existing int-types can hold(I know the number of digits). Give me some hints, please, how can I convert that number to it's binary representation (so I will have other char* variable, that will consist binary).

Rob Kennedy
  • 161,384
  • 21
  • 275
  • 467
Alecs
  • 2,256
  • 8
  • 32
  • 45
  • i know this is a hw question but, think about what the benefits of binary are and what you know about the string you already have. – L7ColWinters Jan 30 '12 at 13:35
  • Is the number of digits bigger than the larges int type, or the number represented? – Luchian Grigore Jan 30 '12 at 13:35
  • The standard conversion algorithm will require you to have at least multiplication code for those `big int`s. – Nobody moving away from SE Jan 30 '12 at 13:35
  • You haven't said what _it's binary representation_ is: if you're not using machine words, there is no One True Representation. Once you decide what your output is supposed to be (and update the question if you still want help), you'll be a lot closer to knowing the transformation. – Useless Jan 30 '12 at 13:35
  • 2
    What library choices do you have? using some library like GMP this should be a trivial task. – PlasmaHH Jan 30 '12 at 13:35
  • is this homework? if it is, please tell us. – Heisenbug Jan 30 '12 at 13:39
  • it can be counted as a hw - I've found this task and I want to solve it, but can't find how myself so I'm asking for hints. I just want to convert that decimal number in the chat* to binary, I won't need to do any math on it. Without using any libraries, just C. – Alecs Jan 30 '12 at 13:44
  • +1: A simple question which is not easy to answer. A nice brain teaser (unless you chicken out and go for some bigint library). :-) – Frerich Raabe Jan 30 '12 at 14:32

3 Answers3

4

You could use something like the GNU Multiple Precision library that has support for very long numbers.

Abrixas2
  • 3,207
  • 1
  • 20
  • 22
3

You'll need a custom BigInt library. GMP would be a good choice.

rubenvb
  • 74,642
  • 33
  • 187
  • 332
trojanfoe
  • 120,358
  • 21
  • 212
  • 242
2

Just some hints (if you want to implement it by hand).

I did that (homework) this way:

  1. I used an array of unsigned int to store the bit representing the number(using two's complement representation).
  2. I implemented shift and addition operations on that array (with the same semantic of classical integrals type).
  3. Since you can express a number with sum of products I used an algorithm with shift and add(like shown on this post). You can use the position of a single character in the string to generate the right binary representation.

(I don't know if there are better or faster solutions.) I won't post the code, this way you can enjoy to do it yourself ;)

Community
  • 1
  • 1
Heisenbug
  • 38,762
  • 28
  • 132
  • 190
  • 1 I used an array of unsigned int to store the bit representing the number(using two's complement representation) - I think that point is almost what I am asking.. I have decimal in the char*, and I want to translate that decimal into binary – Alecs Jan 30 '12 at 13:58
  • so would `vector` be a suitable _binary representation_ for your purposes? Until you know the answer that, it's hard to be give more detail. – Useless Jan 30 '12 at 14:48
  • I don't think that vector stl implementation guarantee that the vector elements are allocated contiguously. So you can do that even with vectors, but it could probably be less efficient. – Heisenbug Jan 30 '12 at 14:59
  • @Useless see: I have decimal as a string: "129"(can be longer) and I need to receive string "10000001". With this example there is no problems. But first string can be "123456878912345678912345687891635464686135464654687654354654354679876456879643546876467984656786457684656876512345678945632112312", so I can't convert it to any integer type. – Alecs Jan 30 '12 at 15:35
  • @Alecs: think at your string as: 2 * 10^0 + 1*10^1 + 3 *10^2 ... and so on. Since you can implement addition and multiplication like suggested in the linked post, you already have the solution to your problem. – Heisenbug Jan 30 '12 at 15:40
  • Yeah, but you still don't say what you _need_ from the representation: it could be an array of bool, a std::bitset, a vector of integers - they're all _logically_ identical in that you can test and set the value of an arbitrary bit in some logical sequence of binary digits. You could even just use a string and convert from base 10 to base 2. – Useless Jan 30 '12 at 15:43
  • @Heisenbug `std::vector` is required to have constant-time access, so in practise it's unlikely _not_ to be contiguous. – Useless Jan 30 '12 at 15:45
  • @Useless: I think that you can have constant-access time even with a non contiguous array, am I wrong? What would reduce the efficency is the cache coherence. – Heisenbug Jan 30 '12 at 16:26
  • @Heisenbug I will try to think in Ur direction – Alecs Jan 30 '12 at 16:38
  • @Alecs: if you find a better solution, please let me know. – Heisenbug Jan 30 '12 at 16:39