Sign in to follow this  
Chad Smith

Ripple Carry Adder

Recommended Posts

Ok, I will start off saying that this is a school assignment. I will not be asking for the solution to be coded for me or really anything of the sort. I am just looking for some basic ideas for some implementing the algorithm.

The program is asking for me to create a Ripple-Carry Adder. It is to support a maximum of 5 bits. It will add binary numbers only.

Example:
[code]
1011+11=1000
[/code]

I've already written a class and some functions to get input from the user, accept some commands and some arguments with those commands. At this time the program gets the input from the user (I'm taking both numbers in as a string) and converts each one to an integer to get some quick test cases in really and output them to make sure it is taking in the correct information.

All that is left is the algorithm. The online book we are using doesn't explain the algorithm very well though I do understand it I believe. Here is what I am looking at or was thinking. Storing both numbers in their own string variable then go through and loop through each string character (with only a max of 5 bits, their would only really be 5 characters to loop through) to see what to do with it. If their should be a carry or not and all that. Though for some reason I just feel I am totally off and should not have to store it as strings and check each and every character.

I was also looking at holding each number in their own integer array and looping through the arrays to do the ripple carry addition and check for the carries and storing the answer in an int and just return that int.

I just wanted to get some ideas how some of y'all would approach this, more than likely, pretty simple problem. I know I can't ask for answers here and I would never want to as that is not teaching me anything. Though some brainstorming and maybe ideas on what I could do to try and implement it.

Thanks ahead of time!

Share this post


Link to post
Share on other sites
I didn't enjoy assignments like this when I was at uni. It isn't particularly well defined.
The first question that springs to my mind is: What counts as a ripple-carry adder? This is something I would try to clarify with your lecturer.

Without knowing that, there are a variety of possibilities but it isn't clear whether some of them get you any/much credit.
For example:

* Convert binary to decimal integers using bit manipulation, then just add the integers. It's not a ripple-carry adder but it takes the same inputs and produces the same output as one.

* Your idea: Keep the binary numbers as strings (or as a sequence of booleans) and manipulate them with some simple rules. Does that count as a ripple-carry adder? Ripple-carry adders don't really loop through the bits, but does that matter for this exercise?

* Design a 1-bit full adder, chain 5 of them up to one another and parameterise with inputs from the user.

* Design a Wire that can be connected to other Wires via logical operations (logic gates). Connect Wires up so as to model the schematic design of a ripple-carry adder.


I think this is in-keeping with the spirit of GDNet's homework policies. I believe they are in place just to prevent blatant cheating (which doesn't help anyone in the long term) whereas I view this answer, and your question, as a way of helping you to help yourself - which can only be a good thing [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img] Plus you seem sensible about it, your post is well presented, it contains ideas that are yours and you have a respectable rating, that's a whole different thing to someone who's signed up just to paste in their homework sheet and expects an easy ride. Edited by dmatter

Share this post


Link to post
Share on other sites
I appreciate the post dmatter and appreciate your thoughts about my post and more.

I will take your ideas and thoughts into consideration and come back to let you know on my thoughts after I have had time to think it though and see if I could see those in code.

Thanks.

Share this post


Link to post
Share on other sites
Ok I just wanted to post back and say which solution I decided to go with.

I really created two different solutions really but turned in only one. The first solution I created was I just used bit manipulation and added up to get the answer. This of course gave me the same input and output like dmatter posted. Worked perfectly. I talked to my professor though and decided I'd go ahead and go with my original idea.

I took in a command and two arguments. I wrote a really basic processor to take commands and arguments.
Example:
[code]
add 101 11
or
quit
[/code]
These are the only two commands I'd accept. If the user entered the add command then I simply extracted the arguments as a string and then split them up into two different strings/binary numbers. This would give me two numbers to add By doing it this way I could easily do some error checking to make sure the numbers entered were binary, not negative, and did not produce an overflow or were above the max number bits allowed (program asked for that to be 5). I also added leading 0's to the beginning of the strings if both strings/numbers were not equal length. I finally just looped through the number(s) an checked against some simple rules.

if all 3 bits (carry bit also) were 0, I would write down 0 and didn't carry anything. If one of the three bits were 1, I wrote down 1 and carried 0 If two of the three were 1, then I would write down 0 and carry 1. if all three were 1 then I wrote down and carried 1.

In the end I checked to see if there was a carry out, if there was I wrote that down. This then gave me a sum string that I would return.

I felt doing it this way would be better than just turning in a program that just did bit manipulation to give me the output. I felt this "followed" the algorithm a bit more and used the rules of the algorithm.

Share this post


Link to post
Share on other sites
Glad that you figured this out, but one thing I'd just like to double-check:

[quote name='Chad Smith' timestamp='1347750448' post='4980502']
Example:
1011+11=1000
[/quote]

Shouldn't 1011+11=1110

or am I missing something?

Share this post


Link to post
Share on other sites
You're right it should be.
I was writing the original post directly after work that day so I was more than likely tired and not thinking. Thanks for bringing if to my attention though. I'll check it out to see if it was a simple typo on my part or to make sure the example I used isn't giving me the wrong answers.

I think I took that example from my programs description actually. Makes me wonder if they made a typo...

EDIT: when I get home from classes today Ill post my code. I'd be interested in getting some input to see if their we're faster ways I could have used or maybe if people could see some hidden pitfalls in the code I didn't think of.

Share this post


Link to post
Share on other sites
The description of a ripple carry adder in Wikipedia seems pretty streight forward even though it's describing an electronic circuit rather than a program. The main feature of the adder would seem to be that output from adding the previous bits is used as an input when adding the next bits. I would figure understanding the technique the circuit uses is the point of the assignment and your program is expected to follow the technique. I would expect either in this assignment, or a future one, for user input to come into play in which case you'll probably be using strings for input. If it's not currently a requirement, then obviously you don't need to work with strings but knowing what to do may help later. How you manipulate the data and whether you should store your data as a string or an int would be up to you but you should check on any requirements for the output and plan accordingly.

Just noticed you said you handed in the assignment. It sounds to me like you went about it the right way. Edited by kseh

Share this post


Link to post
Share on other sites
Well I handed in the assignment today actually via the site the we use. When the site tested my program for all cases it compiled but it it only passed one input and output test. Though it confuses me and I believe something is wrong on their end.

Example:
[code]
add 101 11
ripple_carry> 1000
ripple_carry> FAIL : Input "add 101 11" did not produce output "1000".
[/code]

It says my program did not output 1000? umm yes it did? It has my output above it. As you can see it did. The funny thing: a couple lines down it tires that exact same input again and it passed it somehow by outputting the same thing.

I have already emailed my department actually to see what the issue may be. It just doesn't make sense how it fails the input and then passes it couple lines down.

Share this post


Link to post
Share on other sites
Sounds like you chose the right solution in the eyes of your professor. When time permits prototyping multiple solutions is often a good thing to try! Seems like you got some worthwhile educational value of this exercise [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img]

I'd be interested to see your solution, my C++ is probably rustier than I'd like it to be though. Edited by dmatter

Share this post


Link to post
Share on other sites
[quote name='dmatter' timestamp='1348274050' post='4982537']
Sounds like you chose the right solution in the eyes of your professor. When time permits prototyping multiple solutions is often a good thing to try! Seems like you got some worthwhile educational value of this exercise [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img]

I'd be interested to see your solution, my C++ is probably rustier than I'd like it to be though.
[/quote]

I'll be posting the solution soon. My C++ is actually rusty too. I have been studying and creating some Windows forms using C# and .NET lately.

Ok I'll go ahead and post it. I would love to have any suggestions on what to fix and look at in the code. Pitfalls? The only slight bug that I know that I have is if the user only enters in one argument. In that case the second argument is automatically said to be what the first argument was.

I myself do feel like that their is a way or algorithm to get away from having to get away from hard coding all the possibilities for the adder. I would love to hear of anyway someone would go about that. Been a while since I was in C++ so I have forgot what was exactly is available to me and what I might have reinvent the wheel with.


EDIT: I posted the code but the forum seemed to cut off some random chunks...I'll try it again in a reply to this one. Edited by Chad Smith

Share this post


Link to post
Share on other sites
[b]EDIT [/b]Hmmm Main.cpp is being cut off early for some reason...I will try again in one more post. Sorry, not trying to spam...
[b]RippleCarryAdder.h[/b]
[source lang="cpp"]//RippleCarryAdder
//Header File for RippleCarryAdder class


//do not include twice
#ifndef RIPPLECARRYADDER
#define RIPPLYCARRYADDER
//include iostream for console input/output
#include <iostream>
//include string for extracting commands and arguments
#include <string>
//string streams for converting string input to int
#include <sstream>
//iomanip for formatting streams
#include <iomanip>

//namespace standard
using namespace std;

class RippleCarryAdder
{
private:
//private variables

//numberOfBits-hold the max number of bits that can be used
//also the max length
unsigned int numberOfBits;
//error message to be printed out
string error;
//private methods
//AddZeros will add leading zero's to the numbers to make them the sae length
void AddZeros(string& number1, string& number2);
//IsBinary will check if the string is a binary string
bool IsBinary(const string& line);
//check the numbers before they are added to make sure they are valid
bool ValidNumbers(const string& number1, const string& number2);

public:
//constructor
RippleCarryAdder(int numberOfBits);

//add the two numbers up, return a string of numbers
//that will be the sum
string Add(string number1, string number2);

};

#endif[/source]
[b]RippleCarryAdder.cpp[/b]

[source lang="cpp"]//RippleCarryAdder.cpp
//implementation of RippleCarryAdder class


//include the header file for the class
#include "RippleCarryAdder.h"

//Constructor implementation
//sets the number of bits usd for the ading
RippleCarryAdder::RippleCarryAdder(int numberOfBits)
{
this->numberOfBits=numberOfBits;
error="Error! ";
}

//Check to see if the numbers are equal length and add leading zeros to make them equal length
void RippleCarryAdder::AddZeros(string& number1, string& number2)
{
//put 0's in front of the numbers/strings to make sure the two numbers are equal
while(number1.length()<number2.length())
{
number1.insert(0, "0");
}
while (number1.length()>number2.length())
{
number2.insert(0, "0");
}
}

//Takes in a string to check if it is binary
//returns true if it is, returns false if it was not binary
bool RippleCarryAdder::IsBinary(const string& line)
{
//loop through all the characters
for(int i=0; i<(int)line.length(); i++)
{
//use the ASCII numbers 48 and 49 to see if the characters in the string are binary
if((int)line[i]!=48 && (int)line[i]!=49)
{
//was not a binary number
return false;
}
}
return true;
}

//takes in the two numbers to check if it is binary
bool RippleCarryAdder::ValidNumbers(const string& number1, const string& number2)
{
//check to make sure the arguments were actually entered
if(number1==""||number2=="")
{
error+="Must enter two arguments!";
return false;
}

//if the input is not binary numbers print out an error
else if(!IsBinary(number1) || !IsBinary(number2))
{
error+="Not a binary number";
return false;
}

else if(number1.length()>numberOfBits||number2.length()>numberOfBits)
{
error+="Too large";
return false;
}
return true;
}

string RippleCarryAdder::Add(string number1, string number2)
{
string sum="";
//hold the carry for every loop
int carry=0;

AddZeros(number1, number2);

if(!ValidNumbers(number1, number2))
{
//numbers werent valid, print out the error message held in sum
return error;
}

//The ripple carry algorithim will loop through each character in the numbers (right->left) and figure out what to do and how to addd
//sum will hold the final number as a string
for(int i=(int)number1.length()-1; i>=0; i--)
{
if(number1[i]=='0' && number2[i]=='0' && carry==0)
{
carry=0;
sum.insert(0, "0");
}
else if(number1[i]=='1' && number2[i]=='0' && carry==0)
{
carry=0;
sum.insert(0, "1");
}
else if(number1[i]=='1' && number2[i]=='1' && carry==0)
{
carry=1;
sum.insert(0, "0");
}
else if(number1[i]=='0' && number2[i]=='1' && carry==0)
{
carry=0;
sum.insert(0, "1");
}
else if(number1[i]=='1' && number2[i]=='1' && carry==1)
{
carry=1;
sum.insert(0, "1");
}
else if(number1[i]=='1' && number2[i]=='0' && carry==1)
{
carry=1;
sum.insert(0, "0");
}
else if(number1[i]=='0' && number2[i]=='1' && carry==1)
{
carry=1;
sum.insert(0, "0");
}
else if(number1[i]=='0' && number2[i]=='0' && carry==1)
{
carry=0;
sum.insert(0, "1");
}
}
//take into account the carry
if(carry==1)
{
sum.insert(0, "1");
}
//take away leading zeros
if(sum[0]=='0')
{
sum.erase(0, 1);
}

//check to see if the sum is greater than the max number of bits allowed
//to check for any overflows
if(sum.length()>numberOfBits)
{
return "Error! Overflow";
}
return sum;
}[/source] Edited by Chad Smith

Share this post


Link to post
Share on other sites
Only way that main.cpp would post in its entirety is if I took all the formatting away...

[CODE]
//Main.CPP
//Main file for Program1
//STARTED ON: 9/13
/*UPDATE 1:
*basic commands working, user can type in commands
*TO DO: refactor code for cleaner command processing
*/
#include <iostream>
#include "RippleCarryAdder.h"
//C++ standard namespace
using namespace std;
//FUNCTION PROTOTYPES
//GetInput will take in the input for the string and return the input taken.
string GetInput();
//ExtractCommad will extract the commad that was entered
string ExtractCommand(string& line);
//ExtractArgument will extract the argument/arguments entered
string ExtractArgument(string& line);
//ProcessCommand will process the command that the user entered
string ProcessCommand(string& line);
//ProcessArgument will process the argument that the user entered
//take in the arguments, and the two strings you want to store the arguments in
void ProcessArgument(string& line, string& argument1, string& argument2);

//main function where the program starts
int main()
{
//Const string for the beginning text aded to ever cout statement for the user
const string BEGINNING_TEXT="ripple_carry> ";
RippleCarryAdder adder(5);
//two numbers that are processed from the command entered to add up
string number1, number2;
//hold the input/command that was entered
string input;
//hold the sum
string sum;
//boolean variable to see when we need to quit the program or not
//true means keep runing the program
//false means the user wants to quit
bool running=true;
while(running)
{
cout<<BEGINNING_TEXT;
number1="";
number2="";
input=GetInput();
if(ProcessCommand(input)=="add")
{
ProcessArgument(input, number1, number2);
cout<<BEGINNING_TEXT<<adder.Add(number1, number2)<<endl;
}
else if(ProcessCommand(input)=="quit")
{
running=false;
}
else
{
cout<<BEGINNING_TEXT<<"Error! Not a valid command."<<endl;
}
}
//returned successfully
return 0;
}
string GetInput()
{
string temp;
getline(cin, temp);
return temp;
}

string ExtractCommand(string& line)
{
//hold the index/location of the space in the command
int index=line.find(" ");
//if the string does not contain a space it will return string::npos
if(index==string::npos)
{
//return the entire line
//no arguments found
return line;
}
else
{
//return the command up until the arguments start
return line.substr(0, index);
}
}
string ExtractArgument(string& line)
{
//hold the index/location of the space in a line
int index=line.find(" ");
//if the string does not contain a space, their are no arguments
if(index==string::npos)
{
return line;
}
else
{
//return a substring
//from one character after the space to the end of the line
//length-index-1 to take account for the characters we don't need and the one space we moved over
return line.substr(index+1, line.length()-index-1);
}
}
string ProcessCommand(string& line)
{
//return a command string
//string will be the command that was extracted
return ExtractCommand(line);
}
//Will take the arguments and split them up into substrings
//The two references will hold the two different arguments and where you want to store them.
void ProcessArgument(string& line, string& argument1, string& argument2)
{
//get the arguments
string arguments=ExtractArgument(line);
//hold the fist space in the arguments to use which numbers are seperate
int index=arguments.find(" ");
//create a substring from the begining to the first space to hold the first argument/number
argument1=arguments.substr(0, index);
//create a substring from after the first space to the next argument
//take into account the index
argument2=arguments.substr(index+1, line.length());
}
[/CODE] Edited by Chad Smith

Share this post


Link to post
Share on other sites
One thing I noticed in your code, from what I can see when you're adding zeros to make both strings the same length, you're always adding to argument two. I can't see that you determine that argument two is actually the shorter argument. If argument one is shorter then it will potentially keep adding zeros to argument two infinitely until they match in length.

For the actual addition I would simply count the number of 1s, (though I don't know that this would satisfy the requirements of the assignment). My C++ is atrocious, so I'm not going to try and put in example code just some pseudocode below:

Countbits = 0

If Number1 = 1 then Countbits += 1
If Number2 = 1 then Countbits += 1
If Carry = 1 then Countbits += 1

Select Case Countbits
Case 3
Carry = 1
Return = 1

Case 2
Carry = 1
Return = 0

Case 1
Carry = 0
Return = 1

Case 0
Carry = 0
Return = 0
End select

Share this post


Link to post
Share on other sites
[quote name='Chad Smith' timestamp='1348286364' post='4982566']
I would love to have any suggestions on what to fix and look at in the code. Pitfalls? The only slight bug that I know that I have is if the user only enters in one argument. In that case the second argument is automatically said to be what the first argument was.[/quote]
I have some critiques:

From a design perspective I would suggest that adding isn't really a stateful process, so creating a class isn't really needed - a simple function would be fine (although at uni they seem to want everything to be a class).

One limitation of your approach is that once your adder is created with an overflow limit you cannot use it to add bigger numbers - of course you've deliberately chosen that limitation (and for all I know it's part of the project requirements). I would opt to be flexible about the number of bits, no need to cap it.

I could be failing to spot where, but it looks like your adder builds up an error message though it will never actually use it?

A general point I would prefer not to use the string return value as a means to return either a result or an error message. I would throw an exception or have a separate getError() call.

As was pointed out by PyroDragn you only pad zeros onto your second input, although it could be the first input that needs padding.

There could be some issues with your user input parsing and validation. It's a difficult thing to get right mind you. Imagine if I gave three binary numbers "add 101 001 001".
It's often easier to parse input using C++'s stream extraction operator (>>), using a std::istringstream can help with that too.

[quote]I myself do feel like that their is a way or algorithm to get away from having to get away from hard coding all the possibilities for the adder.[/quote]
I think that PyroDragn's suggestion is a good one, just count the number of bits and act accordingly.

[quote]I would love to hear of anyway someone would go about that. Been a while since I was in C++ so I have forgot what was exactly is available to me and what I might have reinvent the wheel with.[/quote]
I've had an attempt at it, as follows:

[code]
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>

// returns true if the string consists of only 1's and 0's with no other characters
bool isbinary(const std::string & binary)
{
for (std::string::const_iterator bit = binary.begin(); bit != binary.end(); ++bit)
{
if (*bit != '0' && *bit != '1') { return false; }
}
return true;
}

// reads from the stream into the provided string, returns true if the value read was a binary number
bool getbinary(std::istream & is, std::string & out)
{
if (!is) { return false; }
is >> out;
return isbinary(out);
}

std::string ripple_add(const std::string & lhs, const std::string & rhs)
{
// walk from the least-significant bit to most-significant bit
std::string::const_reverse_iterator lhs_bit_iter = lhs.rbegin();
std::string::const_reverse_iterator rhs_bit_iter = rhs.rbegin();

// the carry-over bit
bool carry = false;

// the result, this will be constructed in reverse
std::string result;
result.reserve(std::max(lhs.size(), rhs.size()) + 1); // pre-allocate capacity, including a possible carry-bit

// keep going till we run out of bits
while (lhs_bit_iter != lhs.rend() || rhs_bit_iter != rhs.rend())
{
// extract the values, keep in mind the two strings could be of differing lengths in which case substitute a '0' bit
char lhs_bit = (lhs_bit_iter != lhs.rend() ? *(lhs_bit_iter++) : '0');
char rhs_bit = (rhs_bit_iter != rhs.rend() ? *(rhs_bit_iter++) : '0');

// count the number of '1's
int num_high_bits =
(carry ? 1 : 0) +
(lhs_bit == '1' ? 1 : 0) +
(rhs_bit == '1' ? 1 : 0);

// emit the result and carry bit
carry = num_high_bits == 2 || num_high_bits == 3;
char result_bit = (num_high_bits == 1 || num_high_bits == 3) ? '1' : '0';
result.push_back(result_bit);
}

// include carry bit (if high)
if (carry) { result.push_back('1'); }

// need to reverse the result
return std::string(result.rbegin(), result.rend());
}

int main()
{
for (;;)
{
std::cout << "Enter a command... ";

// read the complete input for parsing
std::string input;
std::getline(std::cin, input);
std::istringstream iss(input);

// extract the command identifier: quit|add
std::string command, rhs, lhs;
iss >> command;

// user entered quit command, terminate now
if (command == "quit") { return 0; }

// user entered add command, be sure we extract two binary operands and nothing else
if (command == "add" &&
getbinary(iss, lhs) &&
getbinary(iss, rhs) &&
!iss.ignore())
{
// add the operands and return to start
std::cout << "Answer: " << ripple_add(lhs, rhs) << std::endl;
continue;
}

// unrecognised command
std::cout << "Oops, please try again..." << std::endl;
}
}[/code] Edited by dmatter

Share this post


Link to post
Share on other sites
[quote name='PyroDragn' timestamp='1348308022' post='4982618']
One thing I noticed in your code, from what I can see when you're adding zeros to make both strings the same length, you're always adding to argument two. I can't see that you determine that argument two is actually the shorter argument. If argument one is shorter then it will potentially keep adding zeros to argument two infinitely until they match in length.
[/quote]
[b]Weird. I thought I added that back in my code before I posted it here. That's been fixed. I was messing with that area of the code before I posted to try to make it a tad bit cleaner. Thanks for noticing it though.[/b]

[quote]
[quote name='dmatter' timestamp='1348355707' post='4982759']
[quote name='Chad Smith' timestamp='1348286364' post='4982566']
I would love to have any suggestions on what to fix and look at in the code. Pitfalls? The only slight bug that I know that I have is if the user only enters in one argument. In that case the second argument is automatically said to be what the first argument was.[/quote]
I have some critiques:

From a design perspective I would suggest that adding isn't really a stateful process, so creating a class isn't really needed - a simple function would be fine (although at uni they seem to want everything to be a class).
[/quote]
[b]It was a requirement for my program to have it as a class. I too thought a simple function would be fine.[/b]
[quote]
One limitation of your approach is that once your adder is created with an overflow limit you cannot use it to add bigger numbers - of course you've deliberately chosen that limitation (and for all I know it's part of the project requirements). I would opt to be flexible about the number of bits, no need to cap it.
[/quote]
[b]Requirement for my program to have it work like that. I agreed also that I should make it more flexible but it was a requirement so I programmed it like that.[/b]

[quote]
I could be failing to spot where, but it looks like your adder builds up an error message though it will never actually use it?

A general point I would prefer not to use the string return value as a means to return either a result or an error message. I would throw an exception or have a separate getError() call.
[/quote]
[b]Point taken on not having a string return value for the error. Though I am outputting the error message when I check for the valid numbers in the Add function. If the ValidNumbers function fails it returns the error message that is outputted.[/b]

[quote]
As was pointed out by PyroDragn you only pad zeros onto your second input, although it could be the first input that needs padding.
[/quote]
[b]Yea...I'm not sure why that is not in my post. After looking at my code again it is there. Gamedev kept cutting off some of my code. It took me like 5 tries to even get my main.cpp file post properly. It kept on randomly cutting off some of my code in some places.[/b]

[quote]
There could be some issues with your user input parsing and validation. It's a difficult thing to get right mind you. Imagine if I gave three binary numbers "add 101 001 001".
It's often easier to parse input using C++'s stream extraction operator (>>), using a std::istringstream can help with that too.
[/quote]
Yea, with it being a while since I programmed in C++ am not 100% confident in the input parsing. I'll study more on it and make changes where needed. Thanks.

[quote]
[quote]I myself do feel like that their is a way or algorithm to get away from having to get away from hard coding all the possibilities for the adder.[/quote]
I think that PyroDragn's suggestion is a good one, just count the number of bits and act accordingly.

[quote]I would love to hear of anyway someone would go about that. Been a while since I was in C++ so I have forgot what was exactly is available to me and what I might have reinvent the wheel with.[/quote]
I've had an attempt at it, as follows:

[code]
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>

// returns true if the string consists of only 1's and 0's with no other characters
bool isbinary(const std::string & binary)
{
for (std::string::const_iterator bit = binary.begin(); bit != binary.end(); ++bit)
{
if (*bit != '0' && *bit != '1') { return false; }
}
return true;
}

// reads from the stream into the provided string, returns true if the value read was a binary number
bool getbinary(std::istream & is, std::string & out)
{
if (!is) { return false; }
is >> out;
return isbinary(out);
}

std::string ripple_add(const std::string & lhs, const std::string & rhs)
{
// walk from the least-significant bit to most-significant bit
std::string::const_reverse_iterator lhs_bit_iter = lhs.rbegin();
std::string::const_reverse_iterator rhs_bit_iter = rhs.rbegin();

// the carry-over bit
bool carry = false;

// the result, this will be constructed in reverse
std::string result;
result.reserve(std::max(lhs.size(), rhs.size()) + 1); // pre-allocate capacity, including a possible carry-bit

// keep going till we run out of bits
while (lhs_bit_iter != lhs.rend() || rhs_bit_iter != rhs.rend())
{
// extract the values, keep in mind the two strings could be of differing lengths in which case substitute a '0' bit
char lhs_bit = (lhs_bit_iter != lhs.rend() ? *(lhs_bit_iter++) : '0');
char rhs_bit = (rhs_bit_iter != rhs.rend() ? *(rhs_bit_iter++) : '0');

// count the number of '1's
int num_high_bits =
(carry ? 1 : 0) +
(lhs_bit == '1' ? 1 : 0) +
(rhs_bit == '1' ? 1 : 0);

// emit the result and carry bit
carry = num_high_bits == 2 || num_high_bits == 3;
char result_bit = (num_high_bits == 1 || num_high_bits == 3) ? '1' : '0';
result.push_back(result_bit);
}

// include carry bit (if high)
if (carry) { result.push_back('1'); }

// need to reverse the result
return std::string(result.rbegin(), result.rend());
}

int main()
{
for (;;)
{
std::cout << "Enter a command... ";

// read the complete input for parsing
std::string input;
std::getline(std::cin, input);
std::istringstream iss(input);

// extract the command identifier: quit|add
std::string command, rhs, lhs;
iss >> command;

// user entered quit command, terminate now
if (command == "quit") { return 0; }

// user entered add command, be sure we extract two binary operands and nothing else
if (command == "add" &&
getbinary(iss, lhs) &&
getbinary(iss, rhs) &&
!iss.ignore())
{
// add the operands and return to start
std::cout << "Answer: " << ripple_add(lhs, rhs) << std::endl;
continue;
}

// unrecognised command
std::cout << "Oops, please try again..." << std::endl;
}
}[/code]
[/quote]
[/quote]

Thanks. I'll check it out and try to take some points in.

Thanks to both of y'all! Edited by Chad Smith

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this