Li Kou daily question - day 39 -67. Binary sum

2022.7.18 Did you brush the questions today ？
 

---

subject ：

Here are two binary strings , Returns the sum of them （ In binary ）.

Input is   Non empty   String and contains only numbers  1  and  0.

analysis ：

Two binary arrays of strings , We need to sum the two arrays , Then output according to the characters in binary form .

Ideas ： Find the result , And then go . Then the following steps are required ：

1. Convert string to integer

2. Integer sum

3. Sum integer to binary

4. Binary to char

5.char To string

analysis ：

1. Summation （ The title does not apply , Because it sets the result very large, resulting in the sum overflow ）

class Solution {
public:
    
    string addBinary(string a, string b) {
    long long res = 0;
    string qwe;
    string ans;
    res= sum_binary(a)+ sum_binary(b);
     // Get the sum result , Now turn to string 
    qwe=int_bin(res, ans);
    cout << 1;
    reverse(qwe.begin(), qwe.end());
    return qwe;

    }
    int sum_binary(string s)
    {
        reverse(s.begin(), s.end());
        int length = s.size();
        long sum = 0;
        for (int i=0;i<length;i++)
        {
            if (s[i] == '1')
            {
                sum = sum +pow(2,i);
            }
        }
        return sum;
    }
    string int_bin(int num,string res)
    {
        int a[100];
        int i = 0;
        char c;
        if (num == 0)
        {
            return "0";
        }
        for (; num > 0; i++)
        {
            a[i] = num % 2;
            num = num / 2;
        }
        //a In the store 010101, Now it's char And insert str
        for (int q = 0; q < i; q++)
        {
            c = a[q]+'0';
            res.push_back(c);
        }
        return res;
    }
   
};

2 Carry method

1. First find the longest array

2.carry As a carry number , The result of each location =carry+a【i】+b【i】

3. The result of each bit is % Handle , Judge whether carry is needed ,

4. Judge the last carry Whether it is 1, yes 1 Then carry

class Solution {
public:
    string addBinary(string a, string b) {
        string ans;
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());

        int n = max(a.size(), b.size()), carry = 0;
        for (size_t i = 0; i < n; ++i) {
            carry += i < a.size() ? (a.at(i) == '1') : 0;
            carry += i < b.size() ? (b.at(i) == '1') : 0;
            ans.push_back((carry % 2) ? '1' : '0');
            carry /= 2;
        }

        if (carry) {
            ans.push_back('1');
        }
        reverse(ans.begin(), ans.end());

        return ans;
    }
};