string to two's complement

[therekz]

If I have a string "52" is there a way to convert this to it's two's complement value(in bits), which is 00110100 WITHOUT converting 52 to an int first...

I would like to store this two's complement number into an array, so the final result would be:

a = {0, 0, 1, 1, 0, 1, 0, 0};

reason I asked without converting it first is because I want to convert:

"12376123699991766715151516189991923132754333161819191273123635631616126336"

to it's two's complement form (bits) and as you may know the number above won't fit into an int or int64

[firedraco]

You could use a library made to handle arbitrary precision integers. I think one is called BigInt or BigNum or something like that, go try google and see what you get.

[Bazzy]

GMP http://gmplib.org/

[therekz]

I can't use a library, I need to implement this on my own....

[Disch]

I dont' see how you're going to do this without a bignum library... unless you write your own mini bignum library.

[jsmith]

It is possible to do this without a big math library. I have code to do arbitrary base
conversions (bases 2-62, limited only by reasonable printable character set) that
I wrote 11 years ago, however I cannot post it here.

The general gist of the solution is to perform long-hand division. In long-hand division,
you only ever have to look at a few digits at a time... well within the 32-bit unsigned
limit.

[therekz]

my purpose here is to write my own bignum class.... my constructor needs to take a string and I want to convert this string to a two's complement and store the bits in a vector

[therekz]

well I can do division only if I can store this number somewhere, but the problem is I can't store this number as an int....

[firedraco]

When you are doing long division, you only need like 2 or 3 digits (as a int is fine), you don't need the whole number.

[therekz]

I mean where can I store this number:

12376123699991766715151516189991923132754333161819191273123635631616126336

if I want to divide it by 2

[firedraco]

jsmith wrote:

The general gist of the solution is to perform long-hand division. In long-hand division, you only ever have to look at a few digits at a time... well within the 32-bit unsigned
limit.

http://en.wikipedia.org/wiki/Long_division

[Disch]

I must be dense... but how do you use long division to convert base 10 to base 2?

I thought about doing a "digit at a time" approach at first too, but my first thought was foiled when I realized the right-most digit of the base 10 number can impact the left-most digit of the base 2 number.

I suppose if you go through every digit and add carry to them... but isn't like like making a miniature bignum lib?

[therekz]

but the result of this long division is not in two's complement right??

[therekz]

I think if some can show a code example to do this via long division that would make a lot of sense as it doesn't make quite much sense to me right now....

[Bazzy]

http://www.trunix.org/programlama/cpp/fred/notes/cpp/misc/decimal2binary.html

[Disch]

@Bazzy: That solution relies on you having the entire number to do math on. How can you do that while only looking at a few digits at a time?


EDIT: oh blah.. I just saw the OP say this:

my purpose here is to write my own bignum class

Nevermind! hahaha

[therekz]

what if the number is negative

[Bazzy]

The first bit should be 0 for positive, 1 for negative

[therekz]

>>That solution relies on you having the entire number to do math on. How can you do that while only looking at a few digits at a >>time?

I still agree with this, I've never seen decimal to binary using:

http://en.wikipedia.org/wiki/Long_division

[helios]

Also, having n bits:
Lowest negative number: -2^(n-1), in binary, 1 followed by n-1 zeroes
-1: n ones

EDIT: All you do is take the string and treat it as a decimal representation of a value. "52" is 5*10+2. The rest is just iterated division by 2 on this array. The main part of the problem is writing the division mechanism. Just use the algorithm you were taught in elementary school.

EDIT 2: I should mention that what you really use is the remainders, not the quotients, to build the binary representation.