3

Possible Duplicate:
Converting string of 1s and 0s into binary value

I would like to convert a binary string to an integer string in c++. e.g:

"000000000010" becomes "2"

I have the following constraint: i can not convert this string to an integer type and then convert it again to string because that binary string can be very huge!

I already tried to do it with stringstream, inserting the binary string to it with the flag std::stringstream::binary and then output the content using the std::dec flag, but it doesn't work

Thank you all in advance.

Community
  • 1
  • 1
jav974
  • 1,022
  • 10
  • 22
  • 4
    Welcome to Stack Overflow! We encourage you to [research your questions](http://stackoverflow.com/questions/how-to-ask). If you've [tried something already](http://whathaveyoutried.com/), please add it to the question- if not, research and attempt your question first, and then come back. – David B Aug 21 '12 at 14:06
  • 2
    This sounds like homework, if it is so, please tag it as such. – PlasmaHH Aug 21 '12 at 14:07
  • In order to fit into an int the string can't be very large, since an int typically only holds 32 bits, making the effective max length of the string 32 characters long. – Dervall Aug 21 '12 at 14:07
  • 1
    This project requires minimum research that you should be able to find yourself without issue. – dans3itz Aug 21 '12 at 14:07
  • So a '1' followed by 106 zeroes should result in the decimal string representation of 2^106 ? – Frerich Raabe Aug 21 '12 at 14:07
  • It's easy to use a hexadecimal output string. 1 hex digit corresponds exactly to 4 binary digits. – Wug Aug 21 '12 at 14:10
  • @JoachimPileborg: according to the constraints, you _cannot_ go through an int; I am afraid simple hand-written arithmetic will be necessary (enough to have a +1 and *2 operations) – Grzegorz Herman Aug 21 '12 at 14:10
  • @GrzegorzHerman I don't think that the problem is solvable without going through an integral representation of some sort. (Of course, if you can seek within the input string, that could be your integral representation.) – James Kanze Aug 21 '12 at 14:32
  • @JamesKanze Sure it's possible: do manual string arithmetic. It sucks, but it's possible. – rubenvb Aug 21 '12 at 15:20
  • @rubenvb Manual string arithmetic is just another form of integer. It requires seeking. I don't think the problem is solvable otherwise. (Of course, while there may be many `BigInteger` classes on the network, I don't know of any which work with data still on disk.) The real question is: how huge is huge? Even a million digits would only require a `BigInteger` with 128 thousand bytes. Quite feasible on today's machines. – James Kanze Aug 21 '12 at 15:59
  • 1
    to anybody who wants to close the question: it is not an exact a duplicate of aforementioned question. The OP clearly states that he need a conversion to string, without any integer intermediate state, so any answer to that question will not work here. – Denis Tulskiy Aug 22 '12 at 11:10

3 Answers3

11

You can construct a std::bitset from a std::string, and use std::bitset::to_ulong or std::bitset::to_ullong to get an integer. Be sure to take care of endianness, it is not done for you.

If you need a string from the integer, use std::to_string.

rubenvb
  • 74,642
  • 33
  • 187
  • 332
  • Umm, the problem statement says that the binary string can be huge, so, presumably, an unsigned long long won't have the capacity to represent the same value. I don't see how endianness comes into play here. – Pete Becker Aug 21 '12 at 14:12
  • Just as Pete states, as I read the question, an integer *string* is required as result type, not an integer type... – codeling Aug 21 '12 at 14:12
  • i can not do that because the number can exceeds an unsigned long long. :/ by the way this is not homework – jav974 Aug 21 '12 at 14:13
  • if you convert it to an integer at some point, it still doesn't respect the fact that the binary might simply be too big for an integer – codeling Aug 21 '12 at 14:20
  • @nyarlathotep true. I missed that. Manual string arithmetic is the only thing possible now. – rubenvb Aug 21 '12 at 14:28
  • i was afraid of that, but i think i have no other choice. – jav974 Aug 21 '12 at 14:33
4

You could go about it like this:

  • create a new output string, containing "0"
  • for each character of the (reversed) original string:
    • multiply the result by 2 (digit by digit, taking care of the carry)
    • if the digit is a '1', add 1 to the result (as above)
  • reverse the result (use std::reverse)
Grzegorz Herman
  • 1,875
  • 11
  • 22
  • as i said i can not do that.. overflow on too large representation – jav974 Aug 21 '12 at 14:19
  • 1
    @jav974: I don't see the problem -- the largest **number** I am dealing with here is a single digit (maybe times 2), so it won't exceed 18 – Grzegorz Herman Aug 21 '12 at 14:20
  • let's say i have a string representing (from right to left) 150 times 1 then 100 times 0 then again 200 times 1. that string's length is 450. I don't know any integer type that can handle 450 bits. May be i didn't understand the way you invite me to proceed :/ – jav974 Aug 21 '12 at 14:38
  • Why reverse? Try your algorithm on "1000". Without reversing should work, reversing will give you "1". – Tadeusz Kopec for Ukraine Aug 21 '12 at 14:41
  • @TadeuszKopec: the natural way to operate on strings (especially if you need to append one, which might be the case here) is left-to-right; arithmetic with carry is done lower-to-higher-magnitude, which is right-to-left -- thus the reversal at the end – Grzegorz Herman Aug 21 '12 at 15:33
  • @jav974: work on **strings** and their individual characters, not integers – Grzegorz Herman Aug 21 '12 at 15:34
  • i try that, i come back after – jav974 Aug 21 '12 at 15:46
0

Off the top of my head, I'd start with an accumulated value of 0 and read the binary string from right to left. For each bit, multiply the accumulated value by 2 and if the bit is 1, add 1 to the accumulated value. If the accumulated value is greater than 9, divide it by 10 and write out the remainder as a character. That will give the decimal characters in reverse order.

Never mind. This doesn't work.

Pete Becker
  • 74,985
  • 8
  • 76
  • 165
  • i can not accumulate the values beacause it would overflow with a string representing more than 64 bits ( and it will ! ) – jav974 Aug 21 '12 at 14:17
  • Off the top of my head, I'd put the conversions in a function, and pass the base as an argument:-). – James Kanze Aug 21 '12 at 14:20
  • @jav974 - no, the accumulated value won't overflow an integer. The divisions by 10 take care of that; it only works with one digit at a time, and the largest value it will see is 19. – Pete Becker Aug 21 '12 at 14:20
  • @jav974 So use an integral type with more than 64 bits. (There are `BigInteger` classes available on the net.) Anyway you do it, there will be some sort of range restriction; just use an appropriately sized integral type. – James Kanze Aug 21 '12 at 14:21
  • @PeteBecker: I guess there should be a "merge answers" option, so we don't have to duplicate comments ;) – Grzegorz Herman Aug 21 '12 at 14:21
  • Sigh. Too early in the morning. This just doesn't work. – Pete Becker Aug 21 '12 at 14:27
  • @PeteBecker You mean you'd do the output conversion on the fly? I don't think that will work. In fact, I'm sure it won't. Consider "110000". The results should be "48". As you describe it, you'll get "3" (since you're only multiplying the accumulated value, not the weight of the 1 you're going to multiply). If you multiply the weight of the bit, the first 1 will give you 16---you output a 6, which isn't right either. In this particular case, it will work if you parse the input from left to right, but I'm pretty sure some larger values will fail. – James Kanze Aug 21 '12 at 14:30
  • @JamesKanze - I beat you to it. I've just updated my answer to reflect this. – Pete Becker Aug 21 '12 at 14:32
  • I would like not to use big integer for that, because my class is meant to be a biginteger ( i do arithmetic operations on a bitset of my own ) – jav974 Aug 21 '12 at 14:40