“This is the 15th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

The title

Given two binary strings, return their sum (in binary).

The input is a non-empty string containing only the digits 1 and 0.

Example 1:

Input: a = “11”, b = “1”

Output: “100”

Example 2:

Input: a = “1010”, b = “1011”

Output: “10101”

Tip:

• Each string consists only of the character ‘0’ or ‘1’.
• 1 <= a.length, b.length <= 10^4
• Strings that are not “0” have no leading zeros.

Their thinking

Method one: binary summation without addition

• For the result of a & B, shift one bit to the left (<< 1) to get the carry digit
• A to the b, xor, which is just an addition without carrying, updates to a
• So let’s figure out what the carry number is and update it to B

/ * * *@param {string} a
 * @param {string} b
 * @return {string}* /
const addBinary = (a, b) = > {
  a = parseInt(a, 2);
  b = parseInt(b, 2);
  while(b ! =0) {
    let carry = a & b;
    a = a ^ b;
    b = carry << 1;
  }
  return a.toString(2);
};
Copy the code

Unfortunately, after we submit the code, it doesn’t work. The reason is that parseInt in JavaScript overflows when converting a large binary to decimal. The following 👇 :

Method two: add bits by bits

• So let’s align a and B, and then we’ll complete the 0
• Add bits from right to left, using the carry variable to record whether to advance 1
• The result of each bit is placed in an RES array and converted to a string

/ * * *@param {string} a
 * @param {string} b
 * @return {string}* /
const addBinary = (a, b) = > {
  while (a.length > b.length) b = '0' + b;
  / / alignment first
  while (a.length < b.length) a = '0' + a;
  let res = new Array(a.length);
  let sum = 0;
  / / carry
  let carry = 0; 
  for (let i = a.length - 1; i >= 0; i--) {
    sum = Number(a[i]) + Number(b[i]) + carry;
    if (sum >= 2) {
      res[i] = sum - 2;
      carry = 1;
    } else {
      res[i] = sum;
      carry = 0; }}if (carry) res.unshift(1); // Add a 1 to the end of the loop
  return res.join(' ');
};
Copy the code

Method 3: Improve the above method based on bit operations

• The result of adding the current bit without carrying is xOR
• The current bit AND yields the current bit’s carry. Consider the previous carry AND calculate the carry for the next iteration

/ * * *@param {string} a
 * @param {string} b
 * @return {string}* /
const addBinary = (a, b) = > {
  while (a.length > b.length) b = '0' + b;
  while (a.length < b.length) a = '0' + a; 
  let res = new Array(a.length);
  let val;              // The sum result of the current bit not carried
  let carry;            // Carry the current bit
  let carryFromBefore = 0;  // Whether the current sum has a carry 1 from the previous digit
  for (let i = a.length - 1; i >= 0; i--) {
    val = Number(a[i]) ^ Number(b[i]);   // add without carry
    carry = Number(a[i]) & Number(b[i]); // Find the carry of the current bit
    if (carryFromBefore) { // There is a carry from the previous digit
      if (val == 0) {
        val = 1;        // Add the carry to 1
      } else {         // Current bit 1 + carry 1 = 2
        carry = 1;      // Forward 1
        val = 0;        // The current bit is 0
      }
    }
    carryFromBefore = carry; // The carry to be used for the next iteration
    res.unshift(val);        // Push from the front of the res array
  }
  if (carry) res.unshift(1); // End of loop, carry, add 1
  return res.join(' ');
};
Copy the code

conclusion

This is Xiaokui 🌻, as long as you turn your heart toward the sun, you will have warmth ~

Let’s overcome the algorithm together!!