• Advertisement
Sign in to follow this  

Unsized string prob!!

This topic is 4521 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

hey guys... I am really perplexed wid this assignment tht i have..which i have to submit tomo. perhaps a lil brainstorming wud've solved it, but i cant figure out the logic yet! I thot to myself.. where wud i find a huge grup of expert programmers.. and so here i am !! Well.. the ques is: "Add 2 Binary numbers of variable length. Length of the no.s may exceed 1000 bits." Lang:C/C++ Now, i think i know how i am gona add 2 bits.. i'll use the bitwise OR operator. But the main prob is input of the numbers!! The first thing tht came to mind was a linked list!! But i am not permitted to use a linked list... or for tht matter any ADT! SO am abs stumped as to how i am gonna enter the string!! Hmmm... i have been thinkin along the lines of using a loop and using GETCH() or something to get the indiv chars... but then where the hell do i store it? If all else fails am gonna use Linked lists and submit the assignment! Plz help... am having a brain-cramp thinkin abt this stuff!! Thank you! Over and out.. Bodhisatva

Share this post


Link to post
Share on other sites
Advertisement
Use an array. Or, if you're permitted to use the STL, use std::vector< bool >. Addition is then a matter of sequential place addition and maintaining the carry. Depending on what data representation you use, it may be easier to expand the smaller operand to the size of the larger, simplifying your addition algorithm.

If you do use an array, you can store unsigned integers in that array, preferrably 16-bit. That's a small space optimization for you, plus you can simply add the integers at each index, storing the result in a 32-bit integer and thus easily handling overflow.

Happy hacking.

Share this post


Link to post
Share on other sites
Thank you for replying... but no i cannot use the STL.
As for using an array, how do i declare it? i dont know the size!
The size of the numbers is not specified!! It can be 1000 bits long or even longer!! so still no joy!! :((
Thanx for replying!!

Over and out..
Bodhisatva

Share this post


Link to post
Share on other sites
Since you don't have much time to do this problem (and it is only adding 2 numbers), I won't give you any complicated suggestions. Are you allowed to use a std::string? If you can then it might get easier.


std::string num1, num2, answer;
// You read in the two numbers.
cin >> num1;
cin >> num2;

if (num1.length() > num2.length())
answer.resize( num1.length() + 1 ); // save a space for carry
else
answer.resize( num2.length() + 1 );

// Then I would loop through the numbers from their end
for(int i = 0; i < answer.size() - 1; ++i)
{
if (i < num1.size() && i < num2.size())
{
// in answer, put (num1[num1.size() - i - 1] - '0') + (num2[num2.size() - i - 1] - '0');

}
else if (i < num1.size())
{
// in answer, put num1[num1.size() - i - 1] - '0'
}
else if (i < num2.size())
{
// in answer, put num2[num2.size() - i - 1] - '0'
}

// Take care of all the carries either in the above step, or here

// Loop through and perform a customized output because they are numbers rather than characters that represent numbers.





This is just part of one possible solution.

Share this post


Link to post
Share on other sites
sorry.. really forgot to mention!!
No i cannot use the string type...(tht wud've solved my probs..totally)! And no special lib fns!!
:((

i have a feelin u have more solns? mabbe i can write somne of the alternate solns... just to show tht i tried!! ;)

Over and out...
Bodhisatva

Share this post


Link to post
Share on other sites
Simply preallocate an array of some size. Once the array is full, allocate a new array twice as large as the old one and copy the old one into the new array and deallocate the old array.

Share this post


Link to post
Share on other sites
hmmm... thts a thot!!
Well.. am off to try crack my ass..(i meant assignment :D)!!
Thanx a lot for yer help!!

Over and out..
Bodhisatva

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement