C++

Forum

 
Multiplying Huge Binary Numbers Pt 2 (My Code)

shamieh (161)
So in an attempt to multiply Binary Numbers. Here is what I've come up with... I've tried debugging and it doesn't make any sense why my code won't work. I think i've been working on it too long. Can anyone take a look and see if I'm missing something obvious here?


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
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
 

#include<iostream>
#include<string>
#include<vector>
using namespace std;

//Global Vector to store result  make sure to reverse result
vector<int> result;
bool firstTime = true;
int globalCounter = 0;

//Add Binary Numbers
void addBinaryNumbers(vector<int> x, vector<int> y)
{
	int carry = 0;
	

	if (firstTime == true)
	{
		for (int i = 0; i < x.size(); i++)
		{
			//Copy result in. It's just + n 0(s)
			result.push_back(x[i]);
		}
		
	}
	else
	{
		globalCounter++;

		for (int i = 0; i < globalCounter; i++)
		{
			//Increase according to how many 0s we need.
			x.insert(x.end(), 0);
		}
		while (x.size() <= y.size())
		{
			x.insert(x.begin(), 0);
		}
		while (y.size() <= x.size())
		{
			y.insert(y.begin(), 0);
		}
	}

	if (firstTime == false)
	{
		result.clear();
		//Main Alg
		for (int i = x.size() - 1; i >= 0; i--)
		{

			//0 + 0
			if (x[i] == 0 && y[i] == 0 && carry == 0)
			{
				result.push_back(0);
				carry = 0;
			}

			//0 + 1 carry = 0
			if (x[i] == 0 && y[i] == 1 && carry == 0)
			{
				result.push_back(1);
				carry = 0;
			}

			//0 + 1 carry 1
			if (x[i] == 0 && y[i] == 1 && carry == 1)
			{
				result.push_back(0);
				carry = 1;
			}

			//0 + 1 & carry = 0
			if (x[i] == 0 && y[i] == 1 && carry == 1)
			{
				result.push_back(0);
				carry = 1;
			}

			//1 + 1
			if (x[i] == 1 && y[i] == 1 && carry == 0)
			{
				result.push_back(0);
				carry = 1;
			}

			//1 + 1 carry = 1
			if (x[i] == 1 && y[i] == 1 && carry == 1)
			{
				result.push_back(1);
				carry = 1;
			}

			//1 + 0 carry 0
			if (x[i] == 1 && y[i] == 0 && carry == 0)
			{
				result.push_back(1);
				carry = 0;
			}

			//1 + 0 carry 1
			if (x[i] == 1 && y[i] == 0 && carry == 1)
			{
				result.push_back(0);
				carry = 1;
			}

		}
	}

	if (firstTime == false)
	{
		reverse(result.begin(), result.end());
		
		//If left with overflow..
		if (carry == 1)
		{
			if (x[0] == 1 && y[0] == 1)
			{
				result.insert(result.begin(), 1);
			}

			if ((x[0] == 1 && y[0] == 0) || (x[0] == 0 && y[0] == 1))
			{
				result.insert(result.begin(), 1);
			}

		}


	}
	
	
}

//Multiply Binary Numbers
void multiplyBinaryNumbers(vector<int> x, vector<int> y)
{
	vector<int> tempvector1;
	vector<int> zero = { 0 };
	int counter = 0;
	firstTime = true;
	
	for (int j = y.size() - 1; j >= 0; j--)
	{
		for (int i = x.size() - 1; i >= 0; i--)
		{
			counter++;
			if (counter < y.size() + 1)
			{
				tempvector1.push_back(x[i] * y[j]);
			}

			if (counter == y.size())
			{
				//Reverse vector so its in correct order
				reverse(tempvector1.begin(), tempvector1.end());

				if (firstTime == true)
				{
					//reset counter
					counter = 0;
					addBinaryNumbers(tempvector1, zero);
					tempvector1.clear();
                                        firstTime == false;
				}
				else
				{
					//reset counter
					counter = 0;
					addBinaryNumbers(tempvector1, result);
					tempvector1.clear();
				}
				
			}
		}
	}
}

int main()
{
	vector<int> x = { 1,0,0,1 };
	vector<int> y = { 0,0,1,1 };
	vector<int> t;
	multiplyBinaryNumbers(x, y);
	cout << "result: ";
	for (int i = 0; i < result.size(); i++)
	{
		cout << result[i];
	}
	system("pause");
}
Last edited on
closed account (48T7M4Gy)
I think you have made it a bit too complicated for youself. Just think how you would do it on paper.

One thing that stands out is carry calculation. All you are doing is adding two numbers. So a small function will solve that.

eg 
1
2
3
4
5
 
void add ( int a, int b, int sum, int carry )
{
   sum = ( a + b ) / 2;
   carry = ( a+ b ) % 2;
}


There are plenty of other ways to do it too, but that's about the simplest I can think of. The advantage it has you don't need line after line of if...else stuff. :)
Last edited on
dhayden (5798)
Why are you putting the result in a global variable? Why not return the resulting vector from the functions?

I'm very suspicious of the firstTime global. When adding two numbers, it shouldn't matter if you're doing it for the first time or the billionth.

It looks like you're storing the numbers so that num[0] is the most significant digit and num[num.size()-1] is the least significant. I think the code will be a whole lot easier if you reverse this, so num[0] is the least significant. That way num[x] always represents the xth digit for any num. This will slightly complicate your input and output functions, but the math will be whole lot easier.

kemort's function isn't right. It doesn't compute the sum or carry right, it doesn't return any value and it doesn't allow for carrying in. A better version would be:
// add a, b, and carry, which must each be 0 or 1. returns the sum and sets the carry.
// Note that "carry" is an in/out parameter. On input it's the carry in, on output it's the carry out.
1
2
3
4
5
6
 
int add(int a, int b, int &carry)
{
    int sum = a+ b + carry;
    carry = sum/2;
    return sum % 2;
}


Since you're storing each bit in an integer, you can temporarily store a larger value in each bit position. The value of the number in that position will still be X * 2n but we'll allow X to be any value. Then you just need a function that will "normalize" the number by cleaning it up so each bit position contains just a 0 or 1. The version below assumes that position 0 is the LSB. I've added a bunch of debugging statements so you can see how it works.
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
 
string numToString(const vector<int> &num)
{
    string result;
    for (int i=num.size()-1; i>=0; --i) {
        result += num[i]+'0';
    }
    return result;
}

void normalize(vector<int> &num)
{
    int carry=0;
    int sum;

    cout << "normalizing " << numToString(num) << '\n';

    // add each digit, accumulating the carry
    for (unsigned i=0; i<num.size(); ++i) {
        cout << num[i] << "+" << carry;
        num[i] = add(0, num[i], carry);
        cout << "=" << num[i] << " carry " << carry << '\n';
    }
    while (carry) {
        cout << "0+" << carry;
        num.push_back(add(0, 0, carry));
        cout << "=" << num[num.size()-1] << " carry " << carry << '\n';
    }
}


Now adding numbers gets easy:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
vector<int> add(const vector<int> &a, const vector<int> &b)
{
    unsigned  sz = std::min(a.size(), b.size());
    vector<int> result(std::max(a.size(), b.size()), 0);
    size_t i;

    // add the digits that they both have
    for (i = 0; i < sz; ++i) {
	result[i] = a[i]+b[i];
    }

    // one number may have more digits than the other.
    // Check them each. One of these loops won't execute at all
    for (i=sz; i<a.size(); ++i) {
	result[i] = a[i];
    }
    for (i=sz; i<b.size(); ++i) {
	result[i] = b[i];
    }
    normalize(result);
    return result;
}


and a test:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
int main()
{
    vector<int> a, b, c;
    a.push_back(0);
    a.push_back(1);
    a.push_back(0);
    a.push_back(0);
    a.push_back(1);

    b.push_back(1);
    b.push_back(1);
    b.push_back(0);
    b.push_back(1);
    b.push_back(1);

    cout << "adding " << numToString(a) << " + " << numToString(b) << '\n';
    c = add(a,b);
    cout << "sum = " << numToString(c) << '\n';

}

adding 10010 + 11011
normalizing 21021
1+0=1 carry 0
2+0=0 carry 1
0+1=1 carry 0
1+0=1 carry 0
2+0=0 carry 1
0+1=1 carry 0
sum = 101101
Last edited on
closed account (48T7M4Gy)
oops
shamieh (161)
Code Updated
Update: I am now able to multiply 1001 * 0011 & I get the correct result... But I tried multiplying 1111 * 0101 and got: 010011011.. Here is my updated code.

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
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
 
#include<iostream>
#include<string>
#include<vector>
using namespace std;

//Global Vector to store result  make sure to reverse result
vector<int> result;
bool firstTime;
int globalCounter = 0;
int COUTCtr = 0;

//print stupdi voector
void printVectorAscending(vector<int> someVector)
{
	if (someVector.size() == 0)
	{
		cout << "Vector is empty" << endl;
	}
	else
	{
		for (int i = 0; i < someVector.size(); i++)
		{
			cout << someVector[i];
		}
	}
}

//Add Binary Numbers
void addBinaryNumbers(vector<int> x, vector<int> y)
{
	int carry = 0;
	COUTCtr++;

	if (firstTime == true)
	{
		for (int i = 0; i < x.size(); i++)
		{
			//Copy result in. It's just + n 0(s)
			result.push_back(x[i]);
		}
	}
	else
	{
		globalCounter++;

		for (int i = 0; i < globalCounter; i++)
		{
			//Increase according to how many 0s we need.
			x.insert(x.end(), 0);
		}
		while (x.size() <= y.size())
		{
			x.insert(x.begin(), 0);
		}
		while (y.size() != x.size())
		{
			y.insert(y.begin(), 0);
		}
	}
	printVectorAscending(x); cout << " + "; printVectorAscending(y); cout << "[" <<COUTCtr << "]" << " = "; 

	if (firstTime == false)
	{
		result.clear();
		//Main Alg
		for (int i = x.size() - 1; i >= 0; i--)
		{

			//0 + 0
			if (x[i] == 0 && y[i] == 0 && carry == 0)
			{
				result.push_back(0);
				carry = 0;
			}

			//0 + 1 carry = 0
			if (x[i] == 0 && y[i] == 1 && carry == 0)
			{
				result.push_back(1);
				carry = 0;
			}

			//0 + 1 carry 1
			if (x[i] == 0 && y[i] == 1 && carry == 1)
			{
				result.push_back(0);
				carry = 1;
			}

			//0 + 1 & carry = 0
			if (x[i] == 0 && y[i] == 1 && carry == 1)
			{
				result.push_back(0);
				carry = 1;
			}

			//1 + 1
			if (x[i] == 1 && y[i] == 1 && carry == 0)
			{
				result.push_back(0);
				carry = 1;
			}

			//1 + 1 carry = 1
			if (x[i] == 1 && y[i] == 1 && carry == 1)
			{
				result.push_back(1);
				carry = 1;
			}

			//1 + 0 carry 0
			if (x[i] == 1 && y[i] == 0 && carry == 0)
			{
				result.push_back(1);
				carry = 0;
			}

			//1 + 0 carry 1
			if (x[i] == 1 && y[i] == 0 && carry == 1)
			{
				result.push_back(0);
				carry = 1;
			}

		}
	}

	if (firstTime == false)
	{
		reverse(result.begin(), result.end());
		
		//If left with overflow..
		if (carry == 1)
		{
			if (x[0] == 1 && y[0] == 1)
			{
				result.insert(result.begin(), 1);
			}

			if ((x[0] == 1 && y[0] == 0) || (x[0] == 0 && y[0] == 1))
			{
				result.insert(result.begin(), 1);
			}

		}
		printVectorAscending(result);
	}
	
	
}

//Multiply Binary Numbers
void multiplyBinaryNumbers(vector<int> x, vector<int> y)
{
	
	vector<int> tempvector1;
	vector<int> zero = { 0 };
	int counter = 0;
	firstTime = true;
	
	for (int j = y.size() - 1; j >= 0; j--)
	{
		for (int i = x.size() - 1; i >= 0; i--)
		{
			counter++;
			if (counter < y.size() + 1)
			{
				tempvector1.push_back(x[i] * y[j]);
			}

			if (counter == y.size())
			{
				
				//Reverse vector so its in correct order
				reverse(tempvector1.begin(), tempvector1.end());


				if (firstTime == true)
				{
					//reset counter
					counter = 0;
					addBinaryNumbers(tempvector1, zero);
					tempvector1.clear();
					firstTime = false;
				}
				else
				{
					//reset counter
					counter = 0;
					addBinaryNumbers(tempvector1, result);
					tempvector1.clear();
				}
				
			}
		}
	}
}

int main()
{
	vector<int> x = { 1,1,1,1 };
	vector<int> y = { 0,1,0,1 };

	multiplyBinaryNumbers(x, y);
	cout << "result: ";

	printVectorAscending(result);
	system("pause");
}
dhayden (5798)
Line 39: You assume that result is empty. What if it isn't, such as when you call addBinaryNumbers at line 190? As I said already
don't use a global variable for your return value.
addBinaryNumbers should return a vector<int>

The 53 lines of code from 70-123 can be replaced by the 6 line add() function that kemort and I suggested.

Line 171: If y is 13 bits long and x is 3 bits long then this statement will be true after the 13th pass through the loop. That's after you've multiplied the 3 bits of x by the first 4 bits y, and then multiplied the 1st bit of x by the 1st bit of y. Clearly this is not what you want. I think the logic from lines 174-192 should go after the x loop (i.e., after line 195).

As I said before, I'm very suspicious of the firstTime global. There is no difference between adding binary numbers the 1st time or the 100th time, so why should addBinaryNumbers() care? Also, notice that it doesn't set firstTime. So something is wrong.

I highly HIGHLY recommend that you print the arguments and the result of addBinaryNumbers(). This will help determine if you're adding them correctly, and also if you're calling it correctly in the multiplyBinaryNumbers().

shamieh (161)
You, sir, are correct. Lol thanks so much for the help... I was making this way harder than it needed to be.
Topic archived. No new replies allowed.