陸小鳳原創
本文講解「兩個二進位數相加」的算法題。
小白：陸大俠，你想的題目？
際小鳳：leetcode的題（https://leetcode.com/），leetcode是可以挑戰算法設計的地方。
題目如下：
/*
Given two binary strings, return their sum (also a binary string).
For example,
a = 「11」
b = 「1」
Return 「100」.
*/
如果是c語言，就是實現這樣的一個函數：
char* addBinary(char* a, char* b) {
}
小白：還好我的英文是4.5級。就是有兩個二進位數，求它們的和，並且也表示為二進位數了。很簡單啊，把這兩個數轉成int，再相加，再轉成二進位數就行啦！
陸小鳳：這個做法解決不了數值大小溢出的問題，在字符串很長的情況下是不可行的。故不考慮這個方向。
小白：… 我就知道你會這麼說的。
（1）一個不簡潔的迭代辦法使用迭代的辦法，逐位相加。
如何迭代？
一個while循環。從低位開始，每次取兩個數字及進位相加（如果沒有兩個數字及進位，則迭代結束），記錄本次相加的結果及新的進位值。字符串向高位移動，開始新的一輪迭代。
* 如何相加？
如果按兩個數字跟進位的值來分情況判斷，會繁瑣一點。可以考慮都轉化為int，再三者相加，對結果再分類（比如3時，說明新的進位值為1，並且本次相加的結果為1）。
* 如何向高位移動？
先取得兩個字符串的最小長度為l，迭代時，每次取str[l_each_str-i-1]，i=0 to (l-1)，即可。
* 有哪些細節要注意？
在迭代結束後，還要看進位值是否為1。如果為1，則還需要再次迭代。每次拿剩下的數字，跟進位相加，在進位為0或沒有剩餘數字時結束。迭代結束後，判斷進位的值，如果進位的值為1，則說明產生一個新的數字1。如果進位為0，則需要把剩餘的數字直接作為返回的字符串的內容。
注意最終返回的字符串，在c語言中要以0結尾。
演示代碼
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* addBinary(char* a, char* b) {
int more = 0;
int la = strlen(a);
int lb = strlen(b);
int lmin = la > lb ? lb : la;
int lmax = la > lb ? la : lb;
int retl = lmax + 1;
char* retstr = (char*)malloc(retl);
int i = 0;
while (i < lmin) {
char ca = a[la - i - 1];
char cb = b[lb - i - 1];
int ia = ((ca == '1') ? 1 : 0);
int ib = ((cb == '1') ? 1 : 0);
int temp = ia + ib + more;
if (temp == 3) {
retstr[retl - i - 1] = '1';
more = 1;
}
else if (temp == 2) {
retstr[retl - i - 1] = '0';
more = 1;
}
else if (temp == 1) {
retstr[retl - i - 1] = '1';
more = 0;
}
else {
retstr[retl - i - 1] = '0';
more = 0;
}
i ++;
}
char* left = ((la > lb) ? a : b);
if (more == 1) {
while (i < lmax && more) {
char c = left[lmax - i - 1];
int ic = (c == '1') ? 1 : 0;
int temp = ic + more;
if (temp == 2) {
retstr[retl - i - 1] = '0';
more = 1;
}
else if (temp == 1) {
retstr[retl - i - 1] = '1';
more = 0;
}
i ++;
}
}
if (more == 1) {
retstr[0] = '1';
char* rettemp = (char*)malloc(retl + 1);
memmove(rettemp, retstr, retl);
rettemp[retl] = 0;
free(retstr);
retstr = rettemp;
}
else {
if (i < lmax) {
while (i < lmax) {
char c = left[lmax - i - 1];
retstr[retl - i - 1] = c;
i ++;
}
}
memmove(retstr, retstr + 1, retl - 1);
retstr[retl - 1] = 0;
}
return retstr;
}
int main(int argc, char *argv[])
{
char a[] = "100";
char b[] = "110010";
char* ret = addBinary(a, b);
printf("ret = %s\n", ret);
free(ret);
return 0;
}
在leetcode上的運行時間：3ms。
（2）一個簡潔的c++實現#include <iostream>
#include <algorithm>
using namespace std;
class Solution {
public:
string addBinary(string a, string b) {
int c=0, i=a.size()-1, j=b.size()-1;
string ret;
while (c==1 || i>=0 || j>=0) {
c += i>=0 ? a[i--]-'0' : 0;
c += j>=0 ? b[j--]-'0' : 0;
ret += char(c&1) + '0';
c >>= 1;
}
reverse(ret.begin(), ret.end());
return ret;
}
};
int main(int argc, const char *argv[])
{
string a="100";
string b="110010";
Solution so;
string ret = so.addBinary(a, b);
cout << "ret=" << ret << endl;
return 0;
}
在leetcode上的運行時間：3ms。
公眾號回復"1",拉你進程式設計師交流群
前端必看100本編程書籍
300本編程經典書籍下載
83份A輪、天使輪融資計劃書等你下載
1000G編程教學視頻免費下載，部部經典
100套微信小程序源碼下載
程式設計師必備!!全套微信小程序開發教程
關注公眾號，叫小編發紅包