67 Add Binary
Given two binary strings, return their sum (also a binary string).
For example,
a =
"11"
b ="1"
Return"100".Notes:
- Pointer for non-copy, but allows us to denote max and min.
- Start from the end of the string, and iterate forward. Maintain a carry bit to, to effectively produce a 9 bit adder.
- Reverse string, since we started from the other end.
- Time: O(n + n/2), O(1) space.
string addBinary(string &a, string &b) {
string *bot, *top;
if (a.length() > b.length()) {
top = &a;
bot = &b;
}
else {
top = &b;
bot = &a;
}
int iter_top = top->length() - 1;
int iter_bot = bot->length() - 1;
char carry = '0';
string final;
final.reserve(top->length());
while (iter_bot >= 0) {
if (top->at(iter_top) == '1' && bot->at(iter_bot) == '1') {
if (carry == '1') {
carry = '1';
final += '1';
}
else {
carry = '1';
final += '0';
}
}
else if (top->at(iter_top) == '0' && bot->at(iter_bot) == '1' ||
top->at(iter_top) == '1' && bot->at(iter_bot) == '0') {
if (carry == '1') {
carry = '1';
final += '0';
}
else {
carry = '0';
final += '1';
}
}
else if (top->at(iter_top) == '0' && bot->at(iter_bot) == '0') {
if (carry == '1') {
carry = '0';
final += '1';
}
else {
carry = '0';
final += '0';
}
}
iter_bot--; iter_top--;
}
while (iter_top >= 0) {
if (carry == '1' && top->at(iter_top) == '1') {
carry = '1';
final += '0';
}
else if (carry == '0' && top->at(iter_top) == '1') {
carry = '0';
final += '1';
}
else if (carry == '0' && top->at(iter_top) == '0') {
carry = '0';
final += '0';
}
else if (carry == '1' && top->at(iter_top) == '0') {
carry = '0';
final += '1';
}
iter_top--;
}
if (carry == '1') final += '1';
reverse(final.begin(), final.end());
return final;
}
Last modified 4yr ago