string to two's complement

[Disch]

I don't see any way to do this very efficiently, but here's an inefficient way:

1) Store the base 10 number in string form
2) Look at the low digit. If it's odd, put a '1' in your base 2 array, otherwise put a zero
3) Divide the base 10 number by 2
4) Repeat

Dividing the number by 2 involves stepping through each digit:
a) divide the low digit by 2, then add 5 if the next digit up is odd
b) repeat for each digit, starting from low and moving up


EDIT:

Oh wait... the long division approach just clicked with me... but I wonder if it would really be any faster than the above?

[therekz]

your step fails here in here for big integers:

3) Divide the base 10 number by 2

how can I divide it by two?? I can't do:

1238971237712371631736192731293123188881236136136123613613612361236101010101 / 2

[Disch]

I explain how to divide by 2 just below that. You step through each digit.

[Bazzy]

We already told you to use the long division. This link appeared on a previous post: http://en.wikipedia.org/wiki/Long_division

[therekz]

the low digit you mean:

54141412

5 or 2 in the example above?

this might be out of the league but here's my attempt:

BigInt::BigInt(string s)
{
 int h, p, temp;
 string t = s; 
 char buffer[1];
 for (int i = t.size()-1; i >= 0; i--){
  	if (atoi(t[i]) % 2 == 1)
		temp = 1;
	else
		temp = 0;
		
	vbit.insert(vbit.begin(), temp);

	t = "";
	for (int j = s.size()-1; j >= 0; j--)
	  {	
		p = (atoi(s[i]) / 2);
		if (atoi(s[i-1]) % 2 == 1)
			p+=5;
		itoa(p,buffer,10);
		t.insert(t.begin(), buffer);
	  }
 }

}

[Disch]

low as in the least significant. So 5414412... the low digit is 2.

You have the right idea in your code.. but there are a few mistakes/things I'd change:

- you're using 'i' in that nested loop, but it looks like you meant to use 'j' instead (see lines 17, 18)

- if you're including index 0 in your loops (i >= 0) then you can't index i-1 because that will go out of bounds when i==0. Your best bet is to put an extra '0' at the start of your string (t = ")" + s;) and do i > 0 in your loops.

- it doesn't look like you're changing t properly. You appear to be inserting characters when you divide rather than replacing characters.

- push_front is preferable to insert. Although if you're doing a lot of insertions this way, vector isn't the best choice (I'm assuming that's what vbit is). In fact, vector might be the very worst choice. You may want to consider deque instead.

- you don't need this atoi/itoa nonsense. To convert from a character to a number you just subtract '0':

i = atoi(c);  // boo
i = c - '0';  // yay 

Likewise, you can add '0' to convert back to a character.

Not to mention I don't think your 'buffer' is big enough for atoi/itoa calls anyway (only 1 char wide, no room for the null terminator).

[therekz]

lets talk about the divide by two first:

 for (int j = s.size()-1; j >= 0; j--)
 {	
	p = (atoi(s[j]) / 2);
	if (j-1 >= 0 && (((s[j-1] - '0') % 2) == 1))
 		p+=5;
	itoa(p,buffer,10);
	t.push_front(buffer);
  }

I think I just need help with atoi and itoa

[Disch]

I think you just need to get away from itoa/atoi. They have no place here:

for(j = s.size() - 1; j >= 0; --j)
{
  p = (s[j] - '0') / 2;
  if(j != 0)
  {
    if( (s[j-1] - '0') & 1 )  // same thing as % 2 -- checks if even/odd
      p += 5;
  }
  s[j] = p + '0';   // change the string
}

No itoa, no push_front. We're modifying the number as we divide, we're not prepending the old number with a new number.

[therekz]

here's what I find to be kind of working:

 while(t != "0")
 {
	temp = 0;
  	if ((t[t.size()-1] - '0') % 2 == 1)
		temp = 1;	
		
	result.insert(result.begin(), temp);
		
	u = t;
	t = "";
 	for (int j = u.size()-1; j >= 0; j--)
 	{	
		p = ((u[j] - '0') / 2);
		if (j-1 >= 0 && (((u[j-1] - '0') % 2) == 1))
 			p+=5;
		out << p;
		t.insert(0, out.str());
		out.str("");
 	}
	std::cout << t << std::endl;
 }

just need to make it simpler and my while doesn't work... as sometimes t can be 0, 00, 000, 0000

[Disch]

I don't see how that would work at all.

Why are you inserting in 't'? Isn't that the base 10 number you're dividing? Why would you add digits to it?

You also don't need stringstream. It's way too much for this. It's very simple: When you subtract '0' from an ASCII numerical character, you get its integral value. Likewise when you add '0' to a single digit number, you get the ASCII character for that number.

KISS


EDIT:

Oh I see... you're copying t to u, then erasing t.

That kind of makes sense now. Sorry for flipping out.

[therekz]

of course t has it's initial value, this it because t is divided by 2, so then I need a new value after it's divided by 2.... that's why I insert it to t....

[Disch]

Yeah sorry about that... I get it now ^^

[therekz]

is this what you mean?

t.insert(0, p + '0');

as it doesn't work

[Disch]

*checks string reference*

Apparently there's no overload for insert that takes an index and a char... so you'd need the iterator,char version:

t.insert( t.begin(), p + '0' );

EDIT: if that still gives you an error you can cast it:

t.insert( t.begin(), char(p + '0') );

or just change 'p' to be a char rather than an int.

[therekz]

I really appreciate your help Disch, I've been looking all over the place for this solution from string to binary and no one could help except you... now my question is, what if the number is negative.. my code above simply doesn't work...

[helios]

Flip bits and increment. You should already know all this.