Add Binary

描述

Given two binary strings, return their sum (also a binary string).

For example,

  1. a = "11"
  2. b = "1"

Return 100.

分析

无

代码

  1. // Add Binary
  2. // 时间复杂度O(n)，空间复杂度O(1)
  3. class Solution {
  4. public:
  5.     string addBinary(string a, string b) {
  6.         string result;
  7.         int i = a.length() - 1;
  8.         int j = b.length() - 1;
  9.         int carry = 0;
  11.         while(i >= 0 || j >= 0 || carry > 0) {
  12.             int valueA = i < 0 ? 0 : a[i--] - '0';
  13.             int valueB = j < 0 ? 0 : b[j--] - '0';
  14.             int sum = valueA + valueB + carry;
  15.             result.insert(result.begin(), (sum % 2) + '0');
  16.             carry = sum / 2;
  17.         }
  18.         return result;
  19.     }
  20. };

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/string/add-binary.html