1. 问题描述
Given two binary strings, return their sum (also a binary string).
For example, a = "11" b = "1" Return "100".
Tags: Math String
2. 解答思路
3. 代码
1 #include <stack> 2 #include <string> 3 #include <cctype> 4 using namespace std; 5 class Solution { 6 public: 7 string addBinary(string a, string b){ 8 int aLen = a.size(); 9 int bLen = b.size(); 10 if (0 == aLen) 11 { 12 return b; 13 } 14 if (0 == bLen) 15 { 16 return a; 17 } 18 19 if (aLen >= bLen) 20 { 21 return add(a, b); 22 } 23 else 24 { 25 return add(b, a); 26 } 27 } 28 private: 29 string add(string a, string b) 30 { 31 int nTakeOver = 0; 32 int i = b.size()-1; 33 int j = a.size() - 1; 34 std::string sum = ""; 35 std::string str_0 = "0"; 36 std::string str_1 = "1"; 37 38 for (; i>=0; i--,j--) 39 { 40 int ta = a[j] - '0'; 41 char tb = b[i] - '0'; 42 int r = (ta + tb + nTakeOver) % 2; 43 nTakeOver = (ta + tb + nTakeOver) / 2; 44 if (r == 0) 45 { 46 sum.insert(sum.begin(), str_0.begin(), str_0.end()); 47 } 48 else 49 { 50 sum.insert(sum.begin(), str_1.begin(), str_1.end()); 51 } 52 } 53 if (j<0) 54 { 55 if (nTakeOver == 0) 56 { 57 return sum; 58 } 59 else 60 { 61 sum.insert(sum.begin(), str_1.begin(), str_1.end()); 62 return sum; 63 } 64 } 65 else 66 { 67 while (j>=0) 68 { 69 int ta = a[j] - '0'; 70 int r = (ta + nTakeOver) % 2; 71 nTakeOver = (ta + nTakeOver) / 2; 72 if (r == 0) 73 { 74 sum.insert(sum.begin(), str_0.begin(), str_0.end()); 75 } 76 else 77 { 78 sum.insert(sum.begin(), str_1.begin(), str_1.end()); 79 } 80 j--; 81 } 82 if (nTakeOver == 0) 83 { 84 return sum; 85 } 86 else 87 { 88 sum.insert(sum.begin(), str_1.begin(), str_1.end()); 89 return sum; 90 } 91 } 92 } 93 };