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?

Your getLonger functions seems odd. Whats the point of subtracting '0' from the strings size? — Zaiborg
– Zaiborg, Commented Oct 22, 2020 at 11:17
Some comments to help you come with your own solution: You are calling getLonger multiple times (twice in each loop), but you only need to call it once and store its result. It would be better to zero fill the shorter string, so you do not need to worry about different lenghts. Why don't you do the sum in the reverse order, and then you invert the result? That way, you don't need to worry about carriage (it should be a value that gets tested in each loop and added if needed). It might be a good exercise to read how real machines do it (recommended book: Code, by Charles Petzold) — fern17
– fern17, Commented Oct 22, 2020 at 12:12

dspr · Accepted Answer · 2020-10-22 12:49:11Z

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

lemon · Accepted Answer · 2020-10-22 11:58:48Z

-1

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)

answered Oct 22, 2020 at 11:58

lemon

3501 silver badge7 bronze badges

1 Comment

fern17 Over a year ago

Downvoted because this may confuse the user instead of helping him understand what he is doing wrong.

Collectives™ on Stack Overflow

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

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related