[c++]用字符串实现二进制的加法

87 阅读 0 评论 58 点赞

我是靠谱客的博主默默小土豆，最近开发中收集的这篇文章主要介绍[c++]用字符串实现二进制的加法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述：

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

The input strings are both non-empty and contains only characters 1 or 0.

题目来源：leetcode

java：

 1 public class Solution {
 2     public String addBinary(String a, String b) {
 3         StringBuilder sb = new StringBuilder();
 4         int i = a.length() - 1, j = b.length() -1, carry = 0;
 5         while (i >= 0 || j >= 0) {
 6             int sum = carry;
 7             if (j >= 0) sum += b.charAt(j--) - '0';
 8             if (i >= 0) sum += a.charAt(i--) - '0';
 9             sb.append(sum % 2);
10             carry = sum / 2;
11         }
12         if (carry != 0) sb.append(carry);
13         return sb.reverse().toString();
14     }
15 }

思路：

计算机二进制加法运算：

计算机计算二进制加法是分三部，第一步为将两个加数转换为二进制数，计算两个加数不需要进位的和（利用异或运算 ^ ），得出的结果。第二部将两个加数进行与运算（&）。第三部利用与运算得到结果进行左移运算（<<）（同时为计算两个加数需要进位的和）,得出结果。将或异运算的结果和左移运算的结果作为两个新的加数，重复此操作。直到当与运算的结果为0，则异或运算的结果则为两个加数的和所对应的二进制数。

来源：https://blog.csdn.net/gaoyubo_taili/article/details/79694729

注意事项：

这是一个递归的算法
结果要考虑全为0的情况
除去前端多余的0，用erase函数
刚开始就要把两字符串的长度匹配好

全部代码：

 1 string s_xor(string a,string b)
 2 {
 3     int size=a.size();
 4     string c(size,'0');
 5     for(int i=0;i<size;++i)
 6     {
 7         if(a[i]==b[i]) c[i]='0';
 8         else c[i]='1';
 9     }
10     return c;
11 }
12 string s_and(string a,string b)
13 {  
14     int size=a.size();
15     string c(size,'0');
16     for(int i=0;i<size;++i)
17     {
18         if(a[i]==b[i]&&a[i]=='1') c[i]='1';
19         else c[i]='0';
20     }
21     return c;
22 }
23 bool is_0(string a)
24 {
25 
26 for(int i=0;i<a.size();++i)
27 if(a[i]!='0') return false;
28 return true;
29 }
30 class Solution {
31 public:
32     string addBinary(string a, string b) {
33         int size=a.size()>=b.size()?a.size():b.size();
34         a=string (size-a.size(),'0')+a;
35         b=string (size-b.size(),'0')+b;
36         if(is_0(s_and(a,b)))  {
37     string c=s_xor(a,b);
38     int i=0;
39     if(is_0(c)) return "0";
40     while(c[i]=='0')
41     {
42         c.erase(c.begin()+i);
43     }
44     return c;
45     }
46         else {
47         return addBinary(s_and(a,b)+"0",s_xor(a,b));
48 
49         }
50     }
51 };