integer to two's complement

This is a discussion on integer to two's complement within the C++ Programming forums, part of the General Programming Boards category; what if I want to represent a huge number such as 2^100 to a two's complement, an int definitely can't ...

  1. #1
    Registered User
    Join Date
    Jan 2008
    Posts
    569

    integer to two's complement

    what if I want to represent a huge number such as 2^100 to a two's complement, an int definitely can't handle this....
    Last edited by -EquinoX-; 11-28-2009 at 07:36 PM.

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    There are a lot of large number libraries out there. Some open source ones, and lots of people have their own home made ones.
    My own one is one that stores the binary data in exactly the same way a processor that could handle that number size would, if that's what you're asking.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User
    Join Date
    Jan 2008
    Posts
    569
    I need to implement my own using a vector, and then store digits.... is there any implementation out there that does this?

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    I read one in a book once that used a vector. It's really just a matter of deciding what base you're gonna use and then getting started.
    What operations do you need to support? It may seem hard at first, but once you get started you'll find that addition at least isn't so hard.
    Just make sure you store things least significant value first, that way you can extend it using a simple push_back rather than having to manually resize and move the contents.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Registered User
    Join Date
    Jan 2008
    Posts
    569
    Quote Originally Posted by iMalc View Post
    I read one in a book once that used a vector. It's really just a matter of deciding what base you're gonna use and then getting started.
    What operations do you need to support? It may seem hard at first, but once you get started you'll find that addition at least isn't so hard.
    Just make sure you store things least significant value first, that way you can extend it using a simple push_back rather than having to manually resize and move the contents.
    Operations are +, - and * and bit shifting.. I guess the bit shifting would be easy as it is just shifting elements/bits in the vector... my only problem right now is how to convert those very long string (which is a rep. of a very large integer) to it's two's complement form in bits... or do you guys have any other ways of representing large integer besides a string?

    I already have a constructor that takes an int and int64 and convert those to two's complement form (store it as bits in my vector)... but what if I want to go with a larger number than an int64? use a string? or what? I would really like to avoid storing my base 10 digits (0-9) in my vector... I would like to store bits (1/0) in two's complement as it's easier to do the operations with that form
    Last edited by -EquinoX-; 11-29-2009 at 11:45 AM.

  6. #6
    Registered User
    Join Date
    Apr 2006
    Posts
    2,053
    You just store it like a long number with more than 64 bits. For instance:

    Code:
    char array[2] = {'\0xFC', '\0xFF'}; //represents FFFC which is -4
    Now for a real implementation you will use a resizable vector of ints or longs, but the idea is the same.

    Creating a constructor may be tricky, because you need to decide how a user may specify a large number without using you large number class. But you can just implement a stream reading operator, and not worry about it.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  7. #7
    Registered User
    Join Date
    Jan 2008
    Posts
    569
    basically what I want to do is the following:

    example:

    52 to result in

    00110100

    not

    00000101 00000010

    where 52 is a string here ("52"), not an int... so that I can do this for arbitrary long string

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by -EquinoX- View Post
    basically what I want to do is the following:

    example:

    52 to result in

    00110100

    not

    00000101 00000010

    where 52 is a string here ("52"), not an int... so that I can do this for arbitrary long string
    To store a stringified number in there, you just need to
    1. Start with the value of 0
    2. Multiply by 10
    3. Add the next digit
    4. If there are any more digits, repeat from step 2

    So it turns out that you probably need the multiplication function anyway. That's the funny thing about large number libraries, several of the operations build themselves upon other operations. In fact they almost didn't need to tell you to implement the bitshifts either, because you'd most likely have implemented them anyway for use within the multiplication function.
    You could implement the multipliction by 10 as a special case if you wanted. It' eqivalent to (x<<3) + (x<<1) which is particularly useful if you didn't need to also implement multiplication.

    If you have to convert the number back into a string then it gets harder because then you're forced to implement division as well.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #9
    Registered User
    Join Date
    Nov 2009
    Posts
    82
    I wrote a simple large num lib that used strings and just wrote methods that employ traditional arithmetical (long addition, long division, etc).

    I used stringstream and atoi to translate between chars/ints for the algorithms.

    For example, the algorithm for addition looked like this;
    Carry + A + B = C.
    I would determine what to store and carry from C by turning the int in to a string (stringstream).
    Where M = length of the string;
    Store C[M-1], Carry C[0,M-2] (I would translate the Carry back to an int with atoi(string.c_str())).

    So 123 + 678 would look like this;

    0 + 8 + 3 = 11 -> Store 1, Carry 1
    1 + 7 + 2 = 10 -> Store 0, Carry 1
    1 + 6 + 1 = 8 -> Store 8, Carry 0
    > (Reverse the string chars)

    123 + 678
    Result = 801
    Last edited by since; 11-30-2009 at 10:47 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. memory issue
    By t014y in forum C Programming
    Replies: 2
    Last Post: 02-20-2009, 11:37 PM
  2. Link List math
    By t014y in forum C Programming
    Replies: 17
    Last Post: 02-20-2009, 05:55 PM
  3. Looking for constructive criticism
    By wd_kendrick in forum C Programming
    Replies: 16
    Last Post: 05-28-2008, 09:42 AM
  4. sscanf and 32 bit two's complement
    By The Urchin in forum C++ Programming
    Replies: 4
    Last Post: 10-15-2006, 02:17 AM
  5. load gif into program
    By willc0de4food in forum Windows Programming
    Replies: 14
    Last Post: 01-11-2006, 09:43 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21