在C++中添加二进制数而不使用数组/向量的问题

Question

我正在尝试创建一个简单的程序，它添加了用户提供的2个二进制数字。我尽量不使用向量，所以我使用字符串。这是我到目前为止得到的代码：

#include <iostream>
#include <string>
int getLonger(std::string a, std::string b) {
if ((a.size() - '0') >= (b.size() - '0'))
return 1;
else
return 2;
}
int main() {
std::string n, k, result;
std::cout << "Enter first number: ";
std::cin >> n;
std::cout << "Enter second number: ";
std::cin >> k;
for (int i = 0; i < (getLonger(n, k) == 1 ? n : k).size(); i++) {
if ((getLonger(n, k) == 1 ? k : n)[i]) {
if ((n[i] - '0') + (k[i] - '0') == 2)
result.insert(0, "10");
else
result.insert(0, std::to_string(n[i] - '0' + k[i] - '0'));
}
}
std::cout << result;
}

我正在做很多std::string => int转换，我知道这不太好，但这对我来说不是问题。该代码在100101 + 10101 = 111010上运行良好，但在上失败

1010 + 11 = -24110 (should be 1101)

和

1 + 11 = 10 (should be 100)

我认为影响计算的第一个问题是对2个字符串中较长的一个进行循环。正确的方法可能是通过添加一些字符来调整较小的大小。

第二个是我错误地添加了10，当1 + 1 = 2-程序不携带1时。我试着用一些if statements来修复它，但它没有正常工作。

我使用以下资源来理解二进制加法：http://web.math.princeton.edu/math_alive/1/Lab1/BinAdd.html

如何使我的脚本正确运行？

Answer 1

下面是一个解决方案的示例。我没有处理字符串，而是像往常一样转换数字相加，然后再次转换为二进制字符串：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
int str2num(std::string strNumber) {
int n = 0, i = 0;
std::string reversed(strNumber.rbegin(), strNumber.rend());
for(char c : reversed) {
n += c - '0' ? 1 << i : 0;
i++;
}
return n;
}
// Recursive function
void num2str(int n, std::string &string, int level) 
{ 
if (n > 0)  {
char c = n % 2 + '0';
string += c; 
num2str(n >> 1, string, level + 1); 
}
} 
int main() {
std::string n, k;
n = std::string("1010");
k = std::string("11");
// Conversion in numbers and addition
int a = str2num(n);
int b = str2num(k);
int sum = a + b;

// Conversion to string again
std::string string("");
num2str(sum, string, 0);
std::reverse(string.begin(), string.end());
std::cout << string << "n";
}

Answer 2

我有一个很好的解决方案。

我放了一些javascript代码，如果你愿意，你可以翻译成C++。

重要的数据结构是FSM，您可以尝试通过这种方式来处理此类问题。

您的代码容易出错，而且很难理解。

const str1 = '1010'
const str2 = '11'
const diffLength = Math.abs(str1.length - str2.length);
const fillStr = new Array(diffLength).fill(0).join('');
const [neoStr1, neoStr2] = str1.length > str2.length
? [str1, fillStr + str2]
: [fillStr + str1, str2];
const FSM = {
0: {
0: {
0: [0, 0],
1: [1, 0]
},
1: {
0: [1, 0],
1: [0, 1]
}
},
1: {
0: {
0: [1, 0],
1: [0, 1]
},
1: {
0: [0, 1],
1: [1, 1]
}
}
}
const c1 = neoStr1.split('').reverse()
const c2 = neoStr2.split('').reverse()
let carryBit = 0
const result = c1.map((_, i) => {
const [res, newCarryBit] = FSM[carryBit][c1[i]][c2[i]]
carryBit = newCarryBit
return res
}).reverse().join('')
console.log(carryBit ? carryBit + result : result)