Need Help! Tens Complement - BigInt

ImperfectCoder (23)
Hey guys I'm having an issue with my program. So let me explain what it's supposed to do. So the program has a class of BigInt and the main stores a c-string into a BigInt num. So it will store this c-string convert the c-string into a int return the int then it will convert the int to a string. Then it will also subtract and there will be negatives which is where the tens complement comes into place I think. I'm getting past the first two tests but now when doing the edition I'm getting a negative number but not the right number, any help would be awesome. Thanks in advanced. Bare with me it's a lot of code and I'm refreshing my C++. Also there are more tests but since there is a content limit I just put the first 3.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
 
#include <iostream>

using namespace std;

class BigInt
{
public:
	
	//An empty constructor, the {} is an empty body
	BigInt() {}
	BigInt(const char*);
	BigInt add(const BigInt&);
	BigInt operator+(const BigInt&);
	BigInt subtract(const BigInt&);
	BigInt operator-(const BigInt&);
	string convertToString();
    
private:
	static const int NUM_DIGITS = 100;
	int numArr[NUM_DIGITS];
	void tensComplement();
};

//A constructor which accepts a C string
BigInt::BigInt(const char* str) {
	// TODO: CONVERT C-STRING TO BIGINT
    int len = strlen(str) - 1;
    int zero = NUM_DIGITS - 1;
    for (int i = 0; i < NUM_DIGITS; i++){
		numArr[i] = 48;
    }
    for (int i = len; i >= 0; i--){
        numArr[zero] = str[i];
        zero--;
    }
}

BigInt BigInt::add(const BigInt& rightOperand) {
	BigInt objToReturn("0");
	// TODO: ADD LOGIC HERE
    int carry = 0;
    for (int i = 100; i > 0; i--){
        int left = this->numArr[i] - 48;
		int right = rightOperand.numArr[i] - 48;
        int total = left + right;
        total += carry;
		if (total > 9){
			carry = 1;
		}else{
			carry = 0;
		}
        total = total % 10;
        
        objToReturn.numArr[i] = total + 48;
    }
	//num1 is the this object
	cout << this->numArr[NUM_DIGITS];
    
	//num2 is the rightOperand object
	cout << rightOperand.numArr[NUM_DIGITS];
    
	return objToReturn;
}

BigInt BigInt::operator+(const BigInt& rightOperand){
    cout << "Right OP: " << endl;
	return add(rightOperand);
}

BigInt BigInt::subtract(const BigInt& rightOperand){
	BigInt objToReturn("0");
	// TODO: SUBTRACT LOGIC HERE
	
	return objToReturn;
}

BigInt BigInt::operator-(const BigInt& rightOperand){
	return subtract(rightOperand);
}

string BigInt::convertToString(){
	// TODO: VALUE IN numArr CONVERTED TO STRING
    int count = 0;
    string str;
    if(numArr[0] == 57){
        tensComplement();
    }
    for (int i = 0; i < NUM_DIGITS; i++){
		if(numArr[i] == 48 && count == 0){
            
		}else{
			str.push_back(numArr[i]);
			count++;
		}
    }
    return str;
}

void BigInt::tensComplement(){
	// TODO: TENS COMPLEMENT OF THIS NUMBER
    for (int i = 0; i <= 100; i++) {
        numArr[i] = 9 - numArr[i];
    }
    numArr[NUM_DIGITS] += 1;
    for(int i = NUM_DIGITS; i >= 1; i--){
        if(numArr[i] == 10){
            numArr[i] = 0;
            numArr[i - 1] += 1;
        }
    }
    if(numArr[0] == 1){
        numArr[0] = 9;
    }
}


//This helps with testing.
bool checkTest(string testName, string whatItShouldBe, string whatItIs) {
    
	if (whatItShouldBe == whatItIs) {
		cout << "Passed " << testName << " last digit was: " << whatItIs.at(whatItIs.length()-1) << endl;
		return true;
	}
	else {
		if (whatItShouldBe == "") {
			cout << "**Failed test " << testName << " ** " << endl << "   Output was "<< whatItIs << endl << "   Output should have been blank. " << endl;
		} else {
			cout << "**Failed test " << testName << " ** " << endl << "   Output was "<< whatItIs << endl << "   Output should have been " << whatItShouldBe << endl;
		}
		return false;
	}
}


int main()
{
	BigInt result;
    
	BigInt num1("999");
	BigInt num2("4873");
	BigInt num3("-739");
	BigInt num4("-9871");
	BigInt num5("123456789012345678901234567890");
	BigInt num6("5555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555556");
	BigInt num7("6666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666667");
	BigInt num8("1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111112");
	BigInt num9("-1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000");
	BigInt num10("-30");
	BigInt num11("4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444443");
	BigInt num12("-8999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999");
	BigInt num13("-4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444443");
	BigInt num14("-1");
	BigInt num15("1");
    
	//Tests to see if you even loaded in an BigInt object correctly
	// Test 1
	checkTest("Test 1", "999", num1.convertToString());
	// Test 2
	checkTest("Test 2", "-739", num3.convertToString());
	//Test some addition problems
	// Test 3, negative + negative
	result = num3.add(num4);
	checkTest("Test 3", "-10610", result.convertToString());

	return 0;
}
Last edited on
Duthomhas (13282)
You are using 48 as a magic number. You should be using '0' instead.

Your internal format is confusing you. You are storing the number as digit values '0' through '9' and '-' (which you have not accounted for).

I would store the sign of the number in a distinct boolean field, instead of in the numArr[] itself.

I would also store the digits as the values 0..9, not '0'..'9'. This means you only need to perform the digit to value conversions during to/from string operations, instead of repeatedly during every arithmetic operation you perform.

Make yourself a great big comment block about how it is all done. Then you can refer back to it every time you want to manipulate the bignum.

I would also be inclined to store the number least-significant value to most in the array, but that is me.

When it comes time to add and subtract, both routines must be aware of the sign of the argument values and be prepared to switch to the other method as appropriate:

postive + positive --> add, result is positive
positive + negative --> subtract, result is sign of larger number
negative + positive --> subtract, result is sign of larger number
negative + negative --> add, result is negative

positive - positive --> subtract, result is sign of larger number
positive - negative --> add, result is positive
negative - positive --> add, result is negative
negative - negative --> subtract, result is sign of larger number

The ten's complement should be done during the subtraction operation, not separate from it.

Hope this helps.
ImperfectCoder (23)
Thank you, I'm really gonna sit down(well stand up) and do this on my dry erase board this weekend and go through all the steps of what needs to be done. Today I totally redid the BigInt(const char* str) so I would like your opinion if this looks better and works better. Thanks for the help so far. So now when I do cout << this->numArr[i]; it gives me this which is showing all the numbers right and adding 0 where the '-' is, is this a better approach you think? Also if it is better how do I go about converting this to the string?
9994873073909871123456789012345678901234567890555555555555
5555555555555555555555555555555555555051525354555657585955
5555555555555555555555555555555555555556666666666666666666
6666666666666666666666666666666061626364656667686966666666
6666666666666666666666666666666667111111111111111111111111
1111111111111111111111111011121314151617181911111111111111
1111111111111111111111111112010000000000000000000000000000
0000000000000000000123456789000000000000000000000000000000
0000000000000030444444444444444444444444444444444444444444
4444444041424344454647484944444444444444444444444444444444
4444444443089999999999999999999999999999999999999999999999
9091929394959697989999999999999999999999999999999999999999
9999904444444444444444444444444444444444444444444444440414
2434445464748494444444444444444444444444444444444444444443011
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
BigInt::BigInt(const char* str) {
   // TODO: CONVERT C-STRING TO BIGINT
    int length = NUM_DIGITS - strlen(str);
    int negative = 0;
    
    for (int i = 0; i < 100; i++) {
        numArr[i] = 0;
    }
    
    if(str[length-1] == '-'){
        this->numArr[length-1] = 9;
    }
    
    for(int i = length, k = 0; i < 100; i++, k++){
        char temp = str[k];
        this->numArr[i] = atoi(&temp);
    }
    
    if(negative){
        this->tensComplement();
    }
}


Also here is convert to string but it gives me an output with the right number at the end with leading zeros how can I get rid of those zeros and also the negative is gone so what do I do with that any suggestions.

1
2
3
4
5
6
7
8
9
10
11
12
13
 
string BigInt::convertToString(){
	// TODO: VALUE IN numArr CONVERTED TO STRING
    string str;
    ostringstream convert;
    for(int i = 0; i < 100; i++)
    {
        convert << numArr[i];
        str = convert.str();
        i-=i;
    }
    
    return str;
}
Last edited on
Duthomhas (13282)
Bigints should typically be sign-magnitude. You have no method for remembering the sign of your number.

Also, you are doing something dangerous with atoi() and temp there.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
class BigInt
{
public:
	
	BigInt();
	BigInt(const char*);
	BigInt add(const BigInt&);
	BigInt operator+(const BigInt&);
	BigInt subtract(const BigInt&);
	BigInt operator-(const BigInt&);
	string convertToString();
    
private:
	static const int NUM_DIGITS = 100;
	int numArr[NUM_DIGITS];
	bool isNegative;
	void tensComplement();
};

BigInt::BigInt()
{
	// Always initialize your objects -- the default ctor must do it too
	for (int n = 0; n < NUM_DIGITS; n++)
		numArr[n] = 0;
	isNegative = false;
}

BigInt::BigInt(const char* str)
{
	// 'str' looks like either "123" or "-123"
	// In a text string, the least significant digit is last
	// In our array, the least significant digit is first

	// First, initialize the default value
	for (int n = 0; n < NUM_DIGITS; n++)
		numArr[n] = 0;
	isNegative = false;

	// Next convert the string argument to a BigInt
	if (!str) return;

	if (*str == '-')
	{
		isNegative = true;
		str++;
	}

	for (int n = 0; *str && n < NUM_DIGITS; str++, n++)
	{
		// Get the digit's value
		int digit_value = *str - '0';

		// Validate it
		if (digit_value < 0 || digit_value > 9) break;

		// Assign it
		numArr[n] = digit_value;
	}

	// All done. You might want to check that *str is '\0' 
	// and that isNegative is not true if all the elements are 0
}

Hope this helps.
ImperfectCoder (23)
I really appreciate the help you have been a huge help. So now I checked the numarr and it seems to be storing all the numbers without the '-' and then the isNegative is showing 0 and 1 for each number that is positive and negative. So my question now that I'm recoding the convertostring function is would I just run through the array and if is negative to add the "-" sign back in front while converting it back to a string the values should still be stored there correct? Also when printing out the string I get 9990000000000000etc since I'm not using vector would the push_back still work for this to get rid of the zeros? Again thanks for the help you have been a life saver.

Edit: Sorry for all the questions it's been awhile since i've done C++ and this project piled on me and I wasn't as prepared as I thought. Here is what I have I'm passing the 999 test but I'm getting 739 instead of -739 how do I add that negative sign back in?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
string BigInt::convertToString(){
	// TODO: VALUE IN numArr CONVERTED TO STRING

    int count;
    for(int i = 0; i < NUM_DIGITS; i++){
        int x = numArr[i];
        while(x != 0){
            count = count * 10;
            count = count + x% 10;
            x = x/10;
        }
    }
    string str = to_string(count);
    if(isNegative == true){
        
    }
    return str;
}
Last edited on
ImperfectCoder (23)
So I've been messing around with the
if(isNegative == true){
// iI've tried
str = '-' + str;
// and tried
str.insert('-');

}

I can't seem to get this part working or am I just going way of the program? The first one gives me some -4000 number and the second will give me -39 instead of -739 would I need to make a loop to go through the away moving it over 1 to be able to insert the str?
Duthomhas (13282)
str.insert( 0, "-" );
:O)
ImperfectCoder (23)
That did the trick thank you so much!
ImperfectCoder (23)
Okay so one more hint haha here is what I have now for the program http://pastebin.com/uUMEigJ0 I put it here because it's a large code. So now I need to add them together with since this is a huge different way of going about it I think I'm not sure where to begin. Any tips?

Edit: Here is what I have for adding right now, which is giving me the wrong result I think I'm doing my carrying wrong?

Edit 2: This is what I have now, still getting wrong numbers but closer wrong numbers.
1
2
3
4
5
6
7
8
9
10
11
12
13
 
BigInt BigInt::add(const BigInt& rightOperand){
	BigInt objToReturn("0");
	// TODO: ADD LOGIC HERE
    for (int i = 0; i < NUM_DIGITS; i++) {
        objToReturn.numArr[i] += this->numArr[i] + rightOperand.numArr[i];
        if (objToReturn.numArr[i] > 9) {
            //Reduce by 10
            objToReturn.numArr[i] -= 10;
            objToReturn.numArr[i-1] = objToReturn.numArr[i-1]+1;
        }
    }
    return objToReturn;
}
Last edited on
Duthomhas (13282)
Sorry to have been absent a bit...

Remember, if your numbers are stored in array lsd to msd:

    1234 --> { 4, 3, 2, 1 }

then adding two numbers:

    { 4, 3, 2, 1 }
  + { 4, 7 }

4 + 4 = 8, no carry
3 + 7 = 0, carry
2 + 0 + carry = 3, no carry
1 + 0 = 1

result:

    { 8, 0, 3, 1 } --> 1308



Addition is an operation you can perform directly modifying one of the operands. So, you could have:

1
2
3
4
5
6
7
8
9
10
11
12
 
BigInt& operator += (const BigInt& rightOperand)
{
    ...
    return *this;
}

BigInt operator + (const BigInt& rightOperand)
{
    BigInt result(*this);
    result += rightOperand;
    return result;
}


Hope this helps.
ImperfectCoder (23)
As of right now the array prints out 73900000000000..... And right array prints the 987100000...... I understand the carry part I've tried that out few times I guess my issue is how do I get these arrays to just flip the actual digits ? So to be 93700000... And 17890000000...... Everytime I try to do this it is leading with zeros and then number flipped at the end but it lines up the same as forward and backward so how do I go about flipping just those digits at the beginning and storing them at the beginning still? Thanks again.
Topic archived. No new replies allowed.