Problems with adding binary numbers in C++ without using arrays/vectors

Question

I'm trying to create a simple program, which adds 2 binary numbers provided by the user. I'm trying not to use vectors and so I'm using strings. Here is the code I have got so far:

#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;
}

I'm doing a lot of std::string => int conversion, which I know isn't great, but that's not the problem for me right now. The code works fine on something like 100101 + 10101 = 111010, but fails on:

1010 + 11 = -24110 (should be 1101)

and

1 + 11 = 10 (should be 100)

The first problem that I think affects the calculation is doing the loop on the longer of 2 strings. The correct way would probably be to resize the smaller one by adding some characters.

The second one is my wrong addition of 10, when 1 + 1 = 2 - the program doesn't carry 1. I tried fixing it by using some if statements, but it didn't work correctly.

I used the following resource to understand binary addition: http://web.math.princeton.edu/math_alive/1/Lab1/BinAdd.html

How can I make my script work correctly?

Answer 1

Here is an example of solution. Instead of working with strings, I convert the numbers to add them as usual, then convert again to a binary string :

#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

I have a good solution for this case.

I put some javascript code and you can translate to C++ if you want.

The important data struct is FSM, you can try to clear this way to deal with this kind of question.

Your code is error-prone and hard to understand.

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)